Hi
We went on Uswitch and did a search on what's available in our area, linked to people's reviews of the companies, prices, and speeds. I would really recommend trying it out.
We also then rang a couple of companies. We chose to go with sky - but they messed up big time and forgot to tell BT to upgrade our phoneline meaning we didn't have broadband for nearly two months (and ran up a huge dial up bill as we can't live without the internet). We then plumped for AOL - who I've had before. They set everything up very quickly - well within the 10 days they said it would take, and their helpline was really easy to get through to with staff who knew what they were talking about.
I've heard TalkTalk is very cheap, but I know a few people who've had problems.