Cheaper Is Not the Way
For the purpose of safety I will start of by repeating what other have mentioned: looking for the cheapest place to learn something potentially life-threatening is probably not a good idea. Ask yourself how these places can afford to charge less for the organisation of an activity, and the maintenance of gear, both of which are inherently expensive.
Go Local with Group-Buys
When I first qualified in 2004, the average price for a first scuba diving certification, be it PADI or CMAS, oscillated between 300€ and 400€, back home in Italy. This included renting gear, learning materials, pool training and two or three sea dives (excluding accommodation). However, the recent boom of deal-of-the-day, group-buys and other similar websites has reduced prices of such activities dramatically. You will most probably find a local dive club offering cheap rates for open water certifications on Groupon, for example. Here is a randomly-picked offer at 125$ for Open-Water PADI. Beware the link will inevitably expire soon, but you can do more research yourself.
The main advantage here is that you cut out travel and accommodation costs, since you wont be flying to the Pacific in order to take the course. Obviously, unless you live in places where the seaside offers amazing flora, fauna and landscape, you might have to settle for cold-water dives in quarries (yes UK residents, I am talking to you!). However I would say that this is what you get when looking for the cheapest deal.