There are a lot of things you can do. Generally, the first rule is change the strings. If the intonation is still out, then you will have to do a little more work.
At this point I would recommend taking the guitar to a specialist technician, particularly so if this is your first time setting up a guitar. Even though the guitar was cheap, you have a good chance of messing something up quite badly if you are a bit inexperienced with these sorts of things. Plus, the cost of the setup from the technician will probably bring the total amount spent on the guitar to what a decent low-end guitar would cost anyway.
During the setup, the technician is likely to:
- Adjust the neck and bridge piece so that the action is lower
- File the nut down to correct levels or replace it entirely
- Check the bridge for damage/cracks that could cause bad intonation
- Possibly replace the bridge piece entirely with a 'compensated' saddle.
Cheaper acoustic guitars are likely to have a 'straight' saddle, to keep production costs lower. 'Straight' saddles are not the best at providing good intonation on a guitar.
For details about what 'straight' and 'compensated' saddles are, I'll borrow what I wrote in answer to this questionthis question:
Saddles also come in two different variants: straight and compensated. 'Straight' saddles are straight lines with a rounded top surface that the strings lie over. Compensated ones have recessed and prominent sections (particularly where the top B and E strings are) which aid the intonation, which can be hard to manage on an acoustic guitar.
Hope this helps