Before we go any further: It's fret "dress", not "redress". [/language_nazi] ?
If it's a brand new guitar that has note-outs, I would have it redressed under warranty.
Absolutely, but I have seen many stores who will simply raise the action to get round all but the worst fret nastiness.
No need to change the nut when you dress, you just cut it lower to suit. Chances are if it's a factory setup it's already high anyway and the dress gives you even more meat to play with. Nut work is part and parcel of any fretwork.
Don't have your frets dressed unless it is necessary, but here is where I differ from Gearhead - it's neccessary in many cases. If you're a masochist who likes a high action, or you have been lucky to get the one in a thousand that comes out of the factory with a perfect fret job with no dressing, a dress wont do anything for you, but other than that, it's a way of improving the performance of your guitar - especially if you want a low action with no fret buzz.
The vast majority of guitars under R15K (and even on certain brands in the R30K range), have not been dressed in the factory or are only given a cursory dress, crown and polish if they fail quality control. Now many fret jobs come out pretty decent, but the chances of one coming out perfect are near zero. Fretting is a job that takes manual labour and where humans are involved, there is a certain amount of inconsistency. Frets get seated too hard and compress the wood of the fingerboard and end up low, the process that seats the frets actually presses them out of shape too. There may be debris in the slot that makes the fret stand proud. Even a "perfect" fret job can be confounded by the neck being put under the pressure of the strings, as necks are a different shape under pressure - and may take days to settle properly under tension before you can even tell what needs doing.
