wow, the fish-haters are out in force! Ignore 'em. Fish-eyes are hard to learn to use well, but they can work extremely well in the right circumstances.
Anyway, all fisheyes produce a circular image which directly maps to a hemispherical view, i.e. everything in front of the lens. The difference between a rectilinear lens and fisheye is in its projection, i.e. the relationship between the position of a subject in space and its position on film. For the following, consider the axes to be aligned with the lens, X to the right, Z towards the subject.
For a rectilinear lens, it's simple perspective projection, sort of like a pinhole does:
ximage = f * Xsubject / Zsubject
yimage = f * Ysubject / Zsubject
i.e. the further away it is, the smaller it looks, proportionally.
But a fisheye maps angle-from-centreline into linear distance on the film:
deflection = atan( sqrt(Xsubject2 + Ysubject2) / Zsubject )
rotation = atan2( Ysubject, Xsubject )
ximage = f * deflection * cos (rotation)
yimage = f * deflection * sin (rotation)
or to simplify and just look at something on the x axis:
ximage = f * atan( Xsubject / Zsubject )
See the atan in there, that's the big difference. Units of distance in your image are now units of angle in the scene.
Note that the full view is 180 degrees, or pi = 3.14. Therefore the total diameter of the circular image is 3.14 * f. In reality you usually use only approx 3 * f because it looks really bad at the edges.
The focal length of a fisheye tells you how big the hemispherical image is on the film plane and therefore how much of the scene your film can record; the diameter of the image circle produced is approximately 3x the focal length. If you choose a short fisheye, the circular image will be smaller than your film, and you will see the circle. If you choose a longer fisheye, the film's frame will crop out the edges of the circle and you will get 180 degree coverage corner-to-corner.
If you're shooting 35mm film and don't want a circular image or black corners (full coverage of the film), buy a 15mm or 16mm fisheye. If you want to see the whole circle, buy an 8mm (the circle fits within the 24mm narrow side of your film). At around 12mm, the edges of the circle approximately reach the outer (short) edges of a 35mm frame.