It does work with just the heat sink, but if you want to keep it on for extended periods, the fan is probably a good idea.
I can recommend this kit for a case/fan: http://shop.abopen.com/ - that fan is enough to keep everything feeling cool to the touch.
The design is on Github too, if you want to do your own (and if nothing else the instructions shows you how to hook up a 5v fan directly to the board)
It takes some assembly and very light soldering, but not more than that you can get away with any crappy soldering iron and ideally a pair of wire cutters (but scissors will do)
Uhh... what am I supposed to do with the case that Adapteva has shipped (awaiting arrival) me? The quick start says I need a fan but I do not see any place on the Adapteva case for such a fan. [0,1] Am I supposed to cut and craft the first-party case to work within the documented requirements? =[
Edit: I just noticed that the two cases I posted actually differ. Perhaps the design was not yet settled and they have added provisions for a fan. Does anyone know what the cases that are actually shipping look like?
I don't have the video cable yet and still have to attach the heat sink. They'd really like you to have a fan, so I have some work to assemble one.
http://www.parallella.org/quick-start/