I'm looking to run an immersive/ARG style LARP and I'm trying to block out the time that I'm estimating players will spend on different tasks. One part of this is going to involve puzzle solving, and there is a puzzle which can be solved, but isn't central to the main plot (so the players don't HAVE to solve it). I'd like to know if you guys have any good way of guesstimating the difficulty of a puzzle/mystery or how you plan this thing since I have a finite amount of time to work with and don't want to generate too much content.
The best way is to beta test it. If you have a favorite RPG forum (which is NOT the same as an RPG Q&A site), post it there. Gamers like puzzles and many of them will be happy to try out your puzzle, even if they're not playing in your game.
As previous posters have said, you'll get a huge variation in the time taken to solve the puzzle.
If your puzzle is basically a maths problem, or can be brute forced in some way, you can make a ballpark estimate. Figure out how long it would take you and assume a spread of about 50% - 200% of your time. The more players you have, the more likely the time is to be towards the lower end of the range.
For anything which involves some intuition, you really can't make a reliable estimate. It all depends on whether any of your players think in the same way you do. At a weekend long LARP for 100 players, I've seen puzzles of this type we estimated at 2-3 hours be solved in under a minute and other puzzles we estimated at 10 minutes not be solved at all.
Looking at the second part of your question - "how do you plan this thing" :
1) Since this puzzle isn't central to the main plot, make sure it can be worked on in parallel with the main plot without tying up a significant proportion of the player base.
2) If you would like to see it solved anyway, have one or more clues available for the players to find as they progress down the main plot line.
3) If it is obvious that this isn't part of the main plot, be prepared for the players to totally ignore it.
If you set a specific amount of time instead of leaving the time open ended, you have just effectively sealed off how much time it will take to accomplish a task. This means, however, that you will have to measure success or failure in a different manner, such as with quantity or quality of work. Puzzles involving different configurations, searching for words/images/differences, or alternate solutions to problems would seem to be appropriate for this sort of timed puzzle venture.
If you want to go outside of the box, you can have players do an action that is similar in hand or body movement accomplish another task. ( "Pick this lock? Tie knots in this string. You have 45 seconds.")
If you REALLY want to go outside of the box, you can have the players perform a symbolic action or set of actions to accomplish the task. The action could/should allow for others to assist in the action, and I highly reccommend that the addition of assistants make the action performed exponentially more hillarious. (I,e. Lockpick plays GM in a game of Connect Four. Assistants have to try to tickle the GM with feathers to assist the Lockpicker. Gun-slinger is taking aim at an opponent in game, but out of game he has to hit a target with a pool noodle. Anyone assisting has to hold a pie for the gunman to hit with said pool noodle.) This increases fun for the entire room, especially if the participants don't mind hamming it up. The game within a game also keeps things fresh.