Most companies who host your site will also provide an option to register your domain.
You can reigister a domain online via a web site without the need to talk to anyone.
Note that Gromit above gave the website of Nominet who are the governing body of UK domains, but I dont think you can actually create your domain on their site (anyway they only look after "uk" domains)
A couple of weeks ago I created a new uk site via the website at a hosting company called 1&1 (www.1&1.co.uk) on this page here:
http://order.1and1.co.uk/xml/order/Instant;jse ssionid=06898EA2C7A20C07F9D1C6BBA837CEB1.TC30a ?__frame=_top&__lf=Static
Note that it is more expensive to register a "com" domain than a "uk" domain. In fact the company I used above created my uk domain for free if I hosted the site with them.