I honestly feel just replacing them because you think a cheap amp has cheap tubes is going to either leave you with a false sense of awesomeness that will wear off quickly...
A false sense of awesomeness can last for a long time if you just adopt the proper frame of mind.
One subtle refinement on all the good and true things that have been said so far is that when other aspects of your signal chain become more *transparent*, you'll be able to hear the sound in tubes more. That is, if you have one or more elements in the chain that greatly change the sound (for better or worse), be it the pickup, a bad cable between the guitar and amp, one or more tone altering capacitors in the amp, a particular output transformer, the speakers, etc., then the dominating factor(s) will tend to obscure variations in the tubes. This could be good or bad, depending on how you like the sound.
For instance, I have a mid-80's Marshall half stack that really doesn't sound much different when I put different tubes in it -- a little, sure, but it's definitely the same amp. I chalk it up to the non-tube circuitry, the output transformer, and the 1960A cab with 75 watt Celestions - I *love* this amp. I have a Fender Blues Jr. that I've modded, including adding a Weber speaker, and I can hear tube changes in it a lot more -- even when I move the exact same preamp tubes back and forth between the two amps (they both use 12AX7s, but they have different power tubes, of course).
That said, there's one probably unwanted factor which can be introduced by tubes, and that's noise, generally hiss (and other, even less savory problems like microphonics, but at that point you're talking about bad tubes) -- even in the Marshall, I can reduce or increase hiss a lot by changing tubes.