It creates spaghetti code in that it causes coders to try and split code into states that may not even be necessary, as the ops situation is. When trying to implement a movement system, you may have states where a user is running,walking,swimming,climbing, All of these states will have drastically different logic, so the decoupling makes sense. What is the logic that a "load" state has that can't be implemented in a simpler fashion. But when it comes to situations such as loading a level, moving a large subset of logic to another class instead of having a boolean such as "m_IsLoadingLevel" makes reading code unnecessarily more difficult.

  union 
  {
    int iVal; //4 bytes
    float fVal; //4 bytes
    void* ptrVal; //4 bytes on 32bit OS, 8 bytes on 64 bit OS.
    char strValue[256]; //256 bytes!! 
  }; 

A union's size is equal to the largest object that could be stored in it; in this case, that union's size is 256 bytes, even if a single int is being stored. It basically makes that union pointless. Unions can't resize their memory usage depending on what it is set to, so if you tell the compiler that you might store a 256 byte array in it, it makes *any* usage of that union take up 256 bytes, even if you are storing a single int.

(offtopic, but I thought it a significant enough problem to point out)

I was aware of that, but it was just a simple way to make a variant for passing state data. Technically you can alias to integer/float/etc if necessary, but I like the separation of data types by using a union and just accessing the right types depending on the enum value. *shrug*

I often use method 3 - the exiting state typically explicitly creates the next state, and can therefore set variables, call methods, or even just use the appropriate constructor. But this does create more dependencies and that may not be what you want.

A flexible option is to pass in a map of key/value pairs with the state transition message, which the new state can treat as an arbitrary argument list. But you'll need to have some way of using arbitrary types for the values, which probably means using some sort of variant type. (Or just pass strings for everything, using atoi/atof and similar when you need to get numbers out. Simple is good.)

I don't know if this will help you, but I generally take a different approach to FSMs. I usually define an enumeration of states, then implement each state as a delegate function accepting a data object specific to that state machine.

enum states
{
 state1,
 state2
}
delegate stateDelegate(statedata data);

Dictionary<states, stateDelegate> StateDelegates;

statedata
{
  states State
  int sharedInt
  string sharedString
  object sharedObj
}

void main()
{
   statedelegates.add(state1, State1Delegate)
   statedelegates.add(state2, State2Delegate)

   //If you Require the state to be wrapped in a class
   SomeArbitraryClass sac=new SomeArbitraryClass()
   statedelegates.add(state3, sac.State3Delegate)

   statedata instanceData=new statedata()
   <initialize data>
   while(instanceData.State!=states.exit)
   {
     instanceData=statedelegates[instanceData.State](instanceData);
   }

}

statedata State1Delegate(statedata data)
{
   <do stuff>
   return data
}

statedata State2Delegate(statedata data)
{
  <do stuff>
  return data

}

class SomeArbitaryClass
{
 stateData State3Delegate(Statedata data)
 {
   <Do stuff>
   return data
 }
}

That approach replaces 'global data storage' with a shared statedata object that will grow and grow as the number of potential arguments to different states increases. It might be a reasonable alternative if the states don't need many parameters.

I'm curious about what kinds of parameters are being handed around between states.

The most trivial example is what was stated in the very first post. You have a loading state, and that state needs to know which level to load. Another example might include difficulty level.

Seems like most people just punt this stuff up to singletons or globals, or have some sort of GameManager which is passed to each state and which would end up as a dumping ground for all this data. But maybe there isn't really that much data like this?