As defined by Andy Skelton, Gallery, introduced with WordPress 2.5, is specifically an exposition of images attached to a post. In that same vein, an upload is "attached to a post" when you upload it while editing a post.
In the uploader there is a "Gallery" tab that shows all the uploads attached to the post you are editing. When you have more than one attachment in a post, you should see at the bottom of the Gallery tab a button marked "Insert gallery". That button inserts a shortcode "[gallery]" into the post. WordPress replaces that shortcode with an exposition of all images attached to that post. Non-image file types are excluded from the gallery.
Note: If you don't see the "Insert gallery" button, it may be because you have not attached two images to the post.