What are the usual accommodations in Cape Verde (Cabo Verde in Portuguese)?
We are backpacking, hence looking for cheap but clean options.
Is there anything available for travellers on a budget?
As a general rule, Cape Verde is not very developped for tourism, except in some specific areas (ie. Santa Maria on the island of Sal, which is full of hotels, bed-n-breakfast, & surf-camps).
My impression is that because of this, the range of accommodation options is not very wide.
So most of the times, you have to go for the local hotel or bed-&-breakfast. Price of local hotels usually starts around 38€ for a double room (breakfast included), and 30€ for a single room (breakfast included).
Some of these hotels or bed-&-breakfast can be excellent though. You might run into extremely cheap hotels when in more remote places: e.g. Tarrafal de Montetrigo, on the island of Sant Antao, we paid 15€ for a double room, without breakfast, without hot water, but very clean.
As a rule of thumb, travelling as a group of 2 to 5 people might be the best option to get cheap accommodation. You can then share a bedroom, a flat, and so on (btw: same goes for transportation, hiring a guide, ...).
You rarely find youth hostels, except in some cities. See for instance in Mindello tripadvisor.com/Hotels-g482855-c3-zff26-Mindelo_Sao_Vicente-Hotels.html
A good option is to stay at some local's. You might just ask someone you meet, a taxi driver or else. But it might mean not having hot water and sleeping in rougher conditions (bad mattress, noisy rooster next door, etc). This will be probably the cheapest option, starting around 10€ per night, for 2 people (breakfast not included of course).
Airbnb seems to be a great option in order to get good accommodation at a very decent price. Especially if you are a group of people, and can rent a whole studio/apartement. At the time of writting (2015), Airbnb seems to be developing slowly but surely.
Some organisations also provide services where you can do activities (e.g. hikes) and stay at some local's house. I heard these were very good. Price is not cheap though, as you go through some agency, starting around $200 per person for 3 nights & 4 days.
Wild camping is a great option, many parts of the country are very quiet and several locals told me it was no problem to put your tent in the country side. Or just ask a farmer if you can use a piece of his land. If you look for camping gear, you probably can only get it in the biggest cities (Mindello, Praia, and so on).
CouchSurfing is also an option, although there are not so many members I've been told. I met a few when in Santa Maria (island of Sal) and it was a great experience.