I think people overcomplicate it a bit. I have a few websites and 90% of them have domain names and hosting from the same company as part of the same package. So you just choose your own domain name, go to one of such registrars and they also offer you Web hosting. I can recommend three from a dozen that I used.
1) godaddy.com is probably the most famous, quite cheap.
2) 1and1.com is the second most popular registrar.
3) aruba.it is my personal favourite.
At aruba, for EUR25 a year you can have a domain name and unlimited hosting space. On the other two, it may work out more expensive but they do have special offers on a regular basis so if you keep an eye, you may get a 1 year hosting with a domain for something like EUR1.
Most of my sites are now on aruba, just one on godaddy. I used to have a couple on 1and1, too.
Starting a Web site can in fact begin with just one file. Name it index.html and put it in the root of your server and off you go