Tried this morning and it wasn't there around 7am. Either it wasn't there yet (US store) or it doesn't show up unless you've done the "migration assistant" software update (which I haven't done).
No you don't have to do the Migration upgrade to see Lion in the app store. i haven't done the upgrade and I can see Lion in the App store. It appeared a little after 830est.