I had been riding Ritchie SPD's on my fixie for years (but with a brake) so I wasn't too concerned since I didn't do a TONNE of skidding or skipping...

But then I had a minor crash that busted my brake caliper and nothing else...how perfect! So I went to Toe straps while I got used to relying on my skipping and skidding...

Anyways I used the straps for a long time...but did notice a huge lack in efficiency since I was wearing my old converse shoes most of the time...comfy, but flimsy soles..

So I splurged and got a pair of the Time ATAC XS Carbon pedals...WOW! A little tough at first...clipping in isn't as easy as when you first go to SPDs...but once you're in...you are IN!

I love these things! I know there have been a lot of threads talking about the best clipless pedals for fixies (Especially when brakeless) and I have always been a little paranoid of unclipping with no brakes...

But it didn't even take a day to get 100% confortable with the ATACS (on tension setting 2). I've pulled pretty hard to skid and skip and no casualties (knock on wood).

The float that these babies have is...WEIRD..but I am starting to like it a lot already!

Anyways...to answer your question Skankingbiker...

A shoe for clipless SPD riding can get fairly cheap if you are on a budget...My suggestion is that if this is your first pair...don't buy online (even though I'm an online retailer).

Go and try on some...go for Mountain bike shoes rather than road...much more versatile and comfortable for your first shoes...

Mountain Equipment Coop here in Canada or REI in the states are good places for discount prices on entry level shoes..

You can even get shoes that look like VANS or Airwalks that have cleats..Not the most efficient because of their flexible soles...but definitely comfy..
Just a couple options...