It depends -
It does make some difference. There are really two issues involving registering a domain name. 1 - the actual registration and 2 DNS. Any company can handle the registration itself; it's a pretty simple process. You want to make sure that if you use a cheaper registration company that
YOU own the domain you register. Some of the shady companies actually own the name you register which becomes an issue when you want to change companies later on. They will charge you to "buy" the domain name.
The second issue is DNS. Most registration companies will provide DNS servers. DNS handles resolving the domain name (macrumors.com) to an IP address. DNS also handles MX records - the IP address of the mailserver(s) for a domain. If your hosting company is different than your registration one, you may use either DNS server - or even your own.
Checklist: Do you own the domain with cheap firm? Do they provide DNS server(s)?
I personally use register.com for my personal domain. They are not the cheapest but I have never had an issue with their DNS. I would personally go with a "blue chip" registration company - for me it isn't worth hassel.
Many hosting companies will offer free/cheap registration of a domain name. MAKE SURE YOU OWN THAT NAME or you're stuck with them.
Research hosting companies - one place to look
http://uptime.netcraft.com/perf/reports/Hosters
Hosting really depends on your needs: Do you need SSH access or just some place to put static pages up, or something in between?
