A bunch of dog treats
Fenced in Area
Dressed for the weather (you and your dog :)
Step 1: Treats
Break treats up into smaller parts if you have a smaller dog. (Or if your dog is really good at the game.)
Step 2: Go Outside - Fenced in Yard
If you do not have a fenced in area, a training leash (20'+) would work well in a safe place to play this game. By safe place I mean a field or park not next to a major road or open holes, etc.
Step 3: Game One - Throw and Find
I throw three treats in the snow and then let him find them. Once he has found all three I'll throw three more.
Longer fenced in yard game: When I am shoveling snow and want to keep him entertained I'll throw a handful of treats in the snow. I pick one area of the yard to throw these in. Con: After the game is over he will keep looking for treats every time he is let out (i.e. 4 AM potty time is now a hour look for treats time) so have a very good recall and better treats to entice your dog back into the house.
Step 4: Game Two - Throw and Return
This is just like throwing a tennis ball only they run after the treat eat it and return for you to throw another treat.
This is how I played the game with my previous dog:
Have you dog ready to retrieve I had mine healing next to me.
Throw the treat
Start with throwing the treat very short distances then throw the treat father and father.
If your dog does not return call to have the dog return to you. (When dog returns lots of praise and a treat)
Have your dog do a "trick" (down, sit, ask nicely, etc)
Throw the treat for them to get
Repeat for as long as you like or one (or both) is tired or cold.