How can I customize the style?
You can copy the 'basic.css' file from the package, and then copy it to 'application/blocks/thumbnail_type_gallery/view.css'. You can then modify the CSS to your liking. If you do so, it's recommend to select "No styling" from the block settings, otherwise two CSS files are included.

How can I add a border to each thumb?
.thumbnail-type-gallery .image {
    border: 1px solid #c0c0c0;
}

How can I make sure all thumbnails have the same dimensions?
You can upload all images in the same dimensions, or you can select the 'crop' Resize Mode in your Thumbnail Type settings. This option is available from concrete5 8.2. Another option of course is via CSS.

How can I customize the captions per file?
Go to the Dashboard > File Manager, right click on a file, hit 'Properties' and edit the 'Title' attribute.

How can I change the order of the images in the gallery?
Go the Dashboard > Files > File Sets and click on your File Set. There you can drag your files in the order you want.

I've edited a thumbnail type, but the sizes are still the same
You then have to 'Rescan' the files. You can do this via the File Manager. You'd also install a job for this.