The crafting recipe requires one cookie and one paper.
Upon eating a Fortune Cookie, a Fortune is added to your inventory. The cookie restores one Hunger.
The 'fortunes' inside the cookies contain bits of trivia about minecraft and/or just random sentences, one example being "Good Lord!"
Fortunes do not stack, unless you get the same twice. They do not burn in a furnace.
One Fortune can be converted back to one piece of paper.