I often realize that something is a Monad or an Applicative or what have you after I write out a helper function that I realize it has the same type as >>= or <*> or whatever.
Monads must have the type * -> *. Otherwise you couldn't write out the signatures for >>= and return (which both have "m a" in them).
To over-specify a bit, the type argument corresponds to what the monadic action "returns". So an "m Int" returns an Int. Therefore, the "a" in "State s a" certainly can't be fixed. It has to be whatever that particular state action returns.
Let's pretend for a moment that it makes sense to have a non-fixed "s" parameter.
For example, let's say we had
foo :: State S1 Int
bar :: Int -> State S2 String
OK, so we can't use
(>>=) :: m a -> (a -> m b) -> m b
Because we can't unify "m" with both "State S1" and "State S2". No problem, let's write a new typeclass that has
(>>==) :: m s1 a -> (a -> m s2 b) -> m s2 b
Now, we can have
foo >>== bar :: State S2 String
However, how would you actually go about writing such a thing for the State Monad? The S2 has to come from somewhere, and it's not clear to me here how we're getting from an S1 to an S2. You could certainly embed such transformations (e.g. by including a function of the type S1 -> S2), but that would require an entirely different structure.
As for "effect" vs "side effect", I believe it's just that some people take issue with the fact that "side effect" has the connotation of being accidental. However, most academic materials on the subject do use "side effect", presumably because there are other uses of the word "effect" (e.g. "writing the code this way has the effect of simplifying...").
--Will