Most of the slowdown comes from storing more and more data in the game history as time goes on. Anything which reduces the amount of data stored should help. Besides what n-n suggested, with reducing the number of states stored in the game history, here are a few other tips:
1.) Try to use temporary variables whenever possible.
2.) Once you’re done with a story variable, you should use the <<unset>> macro to get rid of that variable.
3.) Instead of storing any “static” data (data which won’t change during the entire game, e.g. an array holding the names of the days of the week) on a story variable, it should be stored on the setup object variable instead. Data stored there won’t take up space in the game history, but will be accessible both from Twine and JavaScript. (See an example of this in #6 below.)
4.) Instead of using story variables to track certain events, you can use the hasVisited() function to determine if a certain passage where that event occurs has been visited or not.
5.) Instead of using strings, try to store data using number or Boolean variables whenever possible. You can use code or static variables (see #3 above) to translate those values to strings, if needed.
6.) If you want to get really fancy, you can store up to 32 flags as bits on a single number variable using bitwise operators. So you could have something like this in your StoryInit passage:
<<set $flags = 0>>
<<set setup.Flag1 = Math.pow(2, 0)>>
<<set setup.Flag2 = Math.pow(2, 1)>>
<<set setup.Flag3 = Math.pow(2, 2)>>
<<set setup.Flag4 = Math.pow(2, 3)>>
<<set setup.Flag5 = Math.pow(2, 4)>>
...
<<set setup.Flag32 = Math.pow(2, 31)>>
You can use whatever names you want (as long as it only uses A-Z, a-z, 0-9, _, and/or $ in the name and doesn’t start with a number) instead of “Flag#” to make it easier to remember what each flag stands for. (Each flag goes up by a power of 2, since that number represents a single bit.)
You could then set a flag by doing:
<<set $flags |= setup.Flag4>>
or unset a flag by doing:
<<set $flags -= $flags & setup.Flag4>>
Then you can check to see if a flag is set by doing:
<<if $flags & setup.Flag4>>
Flag 4 is set.
<<else>>
Flag 4 is not set.
<</if>>
And while saving up to 31 Boolean values (4 bytes each) may not seem like much, keep in mind that that’s multiplied by the maximum number of states in your game history, so that could be over 12 kB less data for 100 states in the history.
Hope that helps! 
MUCH LATER EDIT: A follow-up to point 6, see the “FlagBit code” section of my Twine/SugarCube sample code collection for some code I created to make doing what I discussed there much easier.