^Drunken Cow and RELEVANT SX
Modern fisheyes for Canon DSLRs don't come too cheap. Here are the usual suspects
Canon 15mm f/2.8 Fisheye
Sigma 8mm f/3.5 Circular Fisheye*
Sigma 15mm f/2.8 Rectilinear Fisheye
Sigma 10mm f/2.8 HSM (silent focusing) Rectilinear Fisheye
Tokina 10-17mm f/3.5-4.5 Rectilinear Fisheye
Peleng 8mm f/3.5 Circular Fisheye* (cheapest but no autofocus)
*The difference between Circular and Rectilinear is that Circular fisheyes take circular pictures, whereas Rectilinear fisheyes have normal rectangular pictures. On a crop body like the Rebel, the circle won't be complete, it will be cut off on the top and the side, but will still have dark curved corners.
Out of all these lenses I have only tried the Sigma 8mm on my Canon 40D. Cool effect, but I was not in love with the lens. At f/3.5, the lens was extremely soft. It would only sharpen up from f/5.6. The front element of the lens is also very vulnerable, as you cannot put front filters on these fisheyes, nor does this model have a built in lens hood for some protection. It's basically a piece of glass curved outward with nothing in it's way.
The Sigma 10mm is the newest, and has HSM, so your focusing will be silent if that is a big factor.
The cheapest out of all these lenses is the Peleng 8mm f/3.5. You can get this for around $300, or somewhere in the ball park. It's a circular fisheye, so if that doesn't bother you, you will be okay. I also read it's pretty heavy. The thing people might have against this lens is it's lack of autofocus. But when you are shooting this wide, focusing won't be much of an issue.