Here in NC, if you want to get a handgun, you've got to get a pistol permit. Costs $5, and you've gotta wait five days. After that? You're in the clear. You buy your pistol, nobody knows but you and the seller. You've gotta buy another permit, though, for another pistol.
Long guns? You go in, you buy it, you sign a paper. Or something along those lines.
Long gun meaning anything that isn't a pistol - so if you want an AK-47 or an AR-15, there's no ridiculous permit process, thank goodness.
Of course, there are always gun shows, too. I'm not sure if a pistol permit is required there, but it's a lot of private sellers, so there's even less paperwork. Gander Mountain is a fantastic store (how can you NOT love a place that has military weapons ranging from the PS-90 to a .50 cal rifle?), but their prices are really high.
I'll tell ya, though, reading some of these stories makes me glad to live in the South! I'd go insane in IL or CA. Sounds like you need a freaking permit for everything except using the bathroom.