Any host that offers PHP and a MySQL database (read: pretty much everyone ) will see you running phpBB in no time. Give ASO a try, cheap hosting but they are reputable.
Where are you located? Because a host can't be recommended without knowing that, as you don't want to have a server and host that's located in another country to you for support reasons.
Ah the UK, the same as me then. Well of course I'll recommend the webhost I'm with as the packages are good, the prices are extremely cheap and the host, service and reliability is outstanding. My host is http://www.tsohost.co.uk and it's with these that I have a Phpbb forum setup. First thing you need to do is get a domain, get your package up and running with a host and then ask back once you have done this and I'll gladly help.
Another fairly cheap UK host is www.web-mania.co.uk, iused them twice, a while back they had a spait of power problems ont he servers but that cleared up, been solid as a rock for months now. £25 a year. Gives you everything you need, and setting up phpBB is extremely simple. Upload the phpBB files and browse to that directory, the wizard does the rest, just follow the instructions