Does a NIOS II need reset?

Oh after downloading his hardware design (thought he was talking about downloading just his code using the IDE). Yes when you download your system design the reset will get triggered, however it's a good design practice to put resets in yourself. Sometimes but not often you can have a PLD not come out of reset properly.

As to your other question, a state machine is different from a processor (althought it's not impossible to make a processor from a state machine, but you'll need to lock yourself in a room for years to achieve this) in that it usually has a finite number of states. They are useful for systems that are not too complicated, but a processor has data stored as variables, so the number of states your processor can have is every combination of values over all memory locations (so lets just call that an infinite state machine).

If you want to see the logic behind a state machine go to the templates in Quartus and call up the state machine with the asyn. reset and that may explain the structure to them (a condition to make you change/stay in a state, and an output dependent on the state you are in).