What do you mean cheap?
You'll easily get accomodation for US$ 8-10. In Cartagena you should opt for somewhere on the Media Luna, the poorer part of town outside the walls. It's only a 5 minute stroll. I prefer La Dorada because it's a lot easier to get the bike in, and you get a room with fan and toilet to yourself. Apparently you can get your bike in the Holiday across the road, but it's a bit more cramped, but is more modern and on the backpacker map. You won't get your bike in Casa Viena.
Santa Marta, loads of places on Calle 11, but I prefer Taganga, the fishing village 5 minutes round the coast. My friends run a great hostel, Moramar, which is in fact where my bike is now - so definitely v.biker friendly! You'll get a great little room for less than COP20,000 and probably for COP16,000 - book ahead. The best alternative is Felipe's which is further up the hill and the main backpacker hang out. You will have to share a room and book ahead.
How much does a man live, after all?
Does he live a thousand days, or one only?
For a week, or several centuries?
How long does a man spend dying?
What does it mean to say “forever”? - Pablo Neruda