In an FSM it is a good idea to two states, one for the asynchronous reset and one for the reset and define them so there is no room for the synthesizer to generate hardware without them.
Use an asynchronous reset if the clock is not available at power up (which is determined by your power and clock design) this will allow the state machine to be set to a known state while the clock is not running. If your designing the schematic, make sure you follow guidelines for generating a clean async signal (if it doesn't have a clean rise time this can create metastablity problems).
You should always have a synchronous reset to memory elements to set the element to a known state.
The code (for memory) look like this (for VHDL). I'm too lazy to write an FSM so I'll copy this counter in to illustrate (just change the counter logic to an FSM (FSM's are very similar to counters):
DACCLK_CNT : process( ARST_L, SYS_CLK)
if ARST_L = '0' then
DAC_COUNT <= 0;
elsif rising_edge(SYS_CLK) then
if DAC_START_H = '1' or DAC_RST_H = '1' then
DAC_COUNT <= conv_std_logic_vector(10#0#, 5);
elsif (DAC_COUNT < conv_std_logic_vector(10#21#, 5) ) then
DAC_COUNT <= DAC_COUNT + 1;
DAC_COUNT <= DAC_COUNT;
ARST_L is an asynchronous reset, and is not gated by the clock. In this particular design it goes high as the power comes on, thus resting everything to a known state.
DAC_RST_H is a clocked reset, and sets the counter (or FSM to a known state).