Work out how much you want to spend on Broadband - depends on where you live and what you can get - ie ADSL(Broadband) via a phoneline or cable from someone like NTL.
You may want to include a phone package to consolidate the entire service and reduce cost.
As an example I use the Pipex mini package which gives me free phone calls & broadband for under £30. Theres hundred of offers out there.
You can go wireless for under £50 if you are buying the kit, but some ISP's will even give you the wireless kit when you join.
If the laptop is already wifi enabled, your new PC will be when you get it, so you will have most of what you need.
You will probably get 1000 replies suggesting which internet provider to choose!