I have set up sites with PROTX, Paypal, Google checkout and HSBC e-payments.
The HSBC is a full on merchant account, there is a lot of code that needs to be added to the site to make it all work, the documentation is good, but there are pages and pages of it. You have to be able to host HTTPS certificates on your site for this to be viable.
I have looked into Lloyds and Natwest FastPay but both seemed difficult to talk the banks about as my clients volume were too low.
PROTX is a merchant account as well albeit smaller (you can have multiple currencies too), you add their code to your site and the details are passed to them for processing, no HTTPS certificate is needed here though.
Google and Paypal are for great, they require little technical knowledge and can be implemented pretty easily.
If you are after a quick and easy setup go for Google (I am personally going away from Paypal because unless the person paying ahs signed up for the instant payment option it can take days and days for the payment to clear).
If you do go down the google route, remember to have a look at Froogleand/or google base - add your products in there as well!
PLEASE NOTE: There are some downloadable stores available that store the card details within the store itself, this is okay if you aer 100% sure the data is safe and no one can access it, if you are going to host your store on a shared server or on a PC in your house, be careful, you have no control over the server access to your (and your clients data).
Make sure the host (or your own interent connection) has a standalone firewall installed and the data in the Database is encrypted.
Sorry for the scary moment, but a guy I met a few months ago got hacked
The BBC article: BBC - London - TV - Is the Internet a fraudster's paradise?
Using merchant sites (google and paypal included) means you are not storing credit cards details so your store will be less of a target.