It depends what you're doing. Press releases can be a handy tool if you're actually announcing news, not that some previously unknown startup by a relatively unknown team has come into existence.

You should pursue coverage as soon as your startup is ready for people to start using it and then at regular intervals thereafter as you add compelling features or have otherwise marketable milestones.