The best way to keep you labware clean is to quickly clean it after each use. If you let the the stains remain and dry, they are much harder to remove.
The rule of thumb when cleaning is to use a similar solvent that was used to create the staining. For example, if you use AP in a beaker and the stain was left behind, try HCl or a clean solution of AP.
Rust is easily removed with muriactic acid.
For more difficult stains try H2SO4 + Hydrogen Peroxide.
Heating the cleaning agent will sometimes assist in the removal of the residues.
You should always use a good quality scrubbing brush to assist with the removal of sediments and caked on debris. Be sure the brush is made of a material that will resist the cleaning agents.
If you know what the stain is composed of you can Google the material name to find solvents for the material.
Soap and hot water works good as a final clean up, but through rinsing is required to remove all traces of the soap before using the labware.
Lastly, a fresh clean coffee filter can occassionally be used to affect removal of stains and crusts inside test tubes and beakers. Wad the filter up and push it tightly into the dry tube/beaker, then rotate the piece around the filter while putting force on the filter. This can in effect scrape off crusts and sediments from the walls (or bottom ) of the piece.
Steve