The only domain registrar I've actually used is GoDaddy. Their site is ugly, their domain parking system is ugly, and you have to be very wary of them putting things into your order that you don't want (they are pushy bastards) so I probably wouldn't go with them. Even so they don't steal your domain name or do any particular funny business so they're begrudgingly alright if you can't find anything else suitable.

One registrar I hear good things about and I would trust are register4less.com. $14.95/yr, and they're sponsored by this very old and respectable web comic called User Friendly that I read. They don't do anything nasty and I think they might just suit your needs. Click here for the User Friendly sponsored part of Register4less (it might be cheaper than the main site, I don't know).

Everything TweaK said about setting up a LAMP stack was right on the money. Fedora and the yum package manager would do the job a lot faster, but if you've got time to spend I always find it more rewarding to configure it all yourself - as you really get a feel for how everything ties together. But it can be frustrating if you don't know what you're doing, so, OK, maybe not.

So it's really as simple as:
1. Buy your domain name from a registrar of your choice. They'll point it to any place of your choosing for a year, upon which you'll have to renew or lose the domain name unless you buy a longer subscription.
2. Get it to point it at your IP. If your IP is not static, you're going to need to perform some Dynamic DNS hocus pocus here, since you're hosting this yourself.
3. Get your server working at that IP.
4. Profit.