It depends on what your difficulty is. KHWiki is an excellent database for these sorts of things, and there it says that:
For the original game:
You cannot unlock it on beginner.
You must complete Jiminy's Journal on standard.
You must finish the game and complete all worlds on proud.
For the final mix/PS3-4 versions:
You must finish the game and complete all worlds, which means that, yes, you have to beat them the second time.
There you go!
EDIT: Do make note that the rest of the article clearly hasn't been updated too much since its conception. A lot of the theories and possible interpretations do stem back all the way to 2006/2007, so any information pertaining that is obviously not canon and clearly speculation that was later confirmed or denied by Birth by Sleep's existence. It's a cool artifact of the fanbase's past, though.