Yes, you remember fisheyes - they were popular back in the 60s and 70s due to their interesting view of the world, and then went out of favour and were not really a sought-after focal length for a long time. They really were a specialist lens, for people who wanted to play with what could be achieved with an ultra-wide angle lens, where everything was basically in focus. The things you can do with a fisheye are pretty cool, however it really does take some thought to get a great fisheye shot.

Minolta 16mm f/2.8 MD Fisheye - by keeping the subject matter at the centre of the frame I have avoided noticeable fisheye distortion, and still obtained an ultra-wide angle
  

I have been an avid user of fisheye lenses for recreational photography since getting my first fisheye in 2002, and when I had my Minolta manual focus gear I had both a 16mm full frame fisheye, and a 7.5mm circular fisheye. A full frame fisheye captures a 180 degree view, from corner to corner, whereas a circular fisheye captures 180 degrees in every direction. Effectively, you can picture this by visualising that a full frame fisheye simply crops a centre rectangle out of a circular fisheye lens.

A fisheye lens can be a difficult tool to use, because straight lines towards the edge of the frame are extremely distorted, resulting in that characteristic fisheye look. The shot above has cleverly disguised this by having no straight lines at the edge of the frame. Additionally the extraordinarily wide field of view can be a challenge to master.

If you think a normal fisheye is a difficult tool, the circular fisheye is something else altogether. As detailed above, a circular fisheye captures 180 degrees, in every direction, including your shoes if you aren't careful. The shot below gives an example of what can be achieved with a circular fisheye.

Minolta 7.5mm f/4 MD Fisheye - This lens has such an extreme depth of field that it is a fixed focus design. Everything from a few inches in front of the lens to infinity is in focus.
  
While shots like those above are fun and interesting, the majority of fisheye shots taken by people are of landscapes, and include the bending of straight lines etc. that is the characteristic sign of a fisheye. After a few shots like this the effect can get a bit old, and so the fisheye has become less popular than traditional rectilinear wide angles for general photography. However, that was then and this is now. With the advent of digital capture, and people becoming more comfortable with manipulation of their images, the fisheye is once more assuming its place as a wide angle lens.

How is it doing this? Through the wonders of "de-fishing" - taking a fisheye photo, and using software to remove the fisheye effect and obtain a wide angle shot in its place. This really started when digital cameras with crop factors of 1.5x or 1.6x needed a wide angle solution, and a fisheye lens offered that possibility. However the same procedure can be used for full frame images for some truly incredible wide angle effects. The examples below show this process at work.

The shot below is taken on my full frame 5D at 16mm, the widest rectilinear lens that I own. This gives you an idea of what a rectilinear superwide lens can achieve, with a angle of view of 108 degrees on a film or full frame digital body.
Canon 5D with Canon EF 16-35mm f/2.8 L lens at 16mm f/8
This is an extremely wide angle lens, providing a sweepingly wide perspective, but it is nothing compared to that of the full frame fisheye. The same view captured by a fisheye is shown below.
 
Canon 5D with Canon EF 15mm f/2.8 at f/8
  
To de-fish the image I use a photoshop plug-in called PTLens that can be obtained here. While optimised for modern autofocus lenses, it works perfectly with any fisheye lens, such as the Minolta 16mm lenses. Using the program you can adjust for distortion, vignetting and chromatic abberation. After processing the image the result looks like this:
"De-fished" Canon 15mm f/2.8 Fisheye image
All that is needed now is for the image to be cropped to remove the black portions of the image. The quality of the image is excellent throughout the central three-quarters of the frame, with only some blurring at the sides due to the stretching of the portions of the frame at the extreme ends of the image. Nevertheless, the final image is quite amazing, and provides an incredible field of view.
The final cropped and defished outcome. To see the field of view of the original 16mm rectilinear shot simply roll your mouse over the image.
  

So you can see that fisheyes aren't necessarily just for people who want 'special effects' type shots. They can be used to obtain images that otherwise would require multiple photographs to be stitched together, and a lot more work. For large prints the quality achieved by stitching multiple images will naturally be better than the fisheye alternative, but for smaller prints this provides a fast and effective way of achieving a good panoramic image, much wider than any rectilinear available.

I hope that this has opened your eyes to some of the uses of fisheye lenses, and excited you to begin experimenting. For my Minolta manual focus readers I recommend one of the Minolta 16mm fisheyes. These are outstanding lenses with built in filters for B&W use, and they provide excellent image quality. Current prices are probably about US$300 - $350 on Ebay, expensive compared to other less-rare Minolta lenses, but quite reasonable for what you are getting. My current Canon EF 15mm f/2.8 Fisheye sells for US$579, and doesn't include any filters.

If this is outside your price range, but you still want to explore fisheye photography, don't buy a fisheye adaptor! These provide terrible quality. Instead look to buy a Zenitar 16mm f/2.8 lens. Readily available on Ebay, these lenses are an M42 mount and cost about $150. With a Minolta-M42 adaptor for another $20 you can be shooting fisheye shots with good quality for a reasonable price. I don't claim the Zenitar will perform at the same level as the Minolta or Canon lenses, but it will be much better than a cheap fisheye adaptor.

A couple of quick reviews of the Zenitar 16mm f/2.8 are available here and here. It seems that build quality can be variable, but overall the opinions appear positive. There are plenty more opinions elsewhere if you are on a low-budget, but personally for Minolta users I would recommend the Minolta lens every time. For Canon users, it depends how much you feel you will use the lens. The Canon lens provides excellent resolution and contrast, and is built well, but it is considerably more expensive. If you feel that you won't use the lens too often, perhaps the Zenitar option is a good alternative.

The interior of the recently renovated Melbourne St Paul's Cathedral with the Canon 5D and Canon EF 15mm f/2.8. A fisheye can really help capture the scope of an impressive building such as this.