Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
I've got a Huzzk case for my MacBook Pro, very good, they do one for the MacBook too.

http://www.huzzk.com/spotz01.html

Not many places sell them, I got mine brand new from ebay.

Definitely recommend it, as it has elastic inside, so you can open and shut you mac with the case still around it. I'd say the Huzzk case protects it very well from small bumps and scratches, however if you wanted something a bit stronger I'd look into the Crumpler School Hymn line. They're more hard back and will make carying the mac a bit bigger, but it should be protected from small drops too.

Craig
 
I got the tom bihn brain cell and then put it in a generic targus laptop bag.
I love it and its got handles or shoulder strap if you just want to carry it.
If you drop it its got protection all over...and no zippers.
I didnt want zippers touching my macbook.
 
I just bought a Macbook, too. If you're looking for a sleeve, then Waterfield is a good bet. I bought a RacerX for my PB G4 and I loved it. If you want a messenger bag, I think this one from Booq is the best. Probably what I will end up getting.

rendit
 
I use an Incase sleeve and a Targus bag. A word of warning- stay away from Radtech Sleevz if you use your laptop everyday (sorry Radtech, I like your other stuff). Mine didn't last 8 months before shredding, and it was also stored in a bag.
 
Still loving the MacCase I got from http://mac-case.com/MacCase Home.htm , and at the time I ordered it for my MacBook they didn't have the MB ones done yet, so they sent me an iBook one for free and shipped the MB one when it was ready. I got the 13" MacBook sleeve, since I carry my MB in a backpack along with my other stuff, rather than one with a handle/strap. It's held up great so far and gets daily use. There were a couple of strands of excess thread on a couple seams, but a quick touch -up with a Bic lighter and there's been no other issues. I will say that this thing fits very snuggly, and if your fingers are the least bit greasy you might have a time getting the notebook out of the sleeve. Maybe that's a good thing because it prevents you from getting greasy fingerprints all over your Mac!;)
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.