There are a few ways to consider how you want to go about using description in your story. Some writers prefer to describe every possible detail all at once, which can help create a clearer mental image for the reader, but also makes the action and progression of the story feel like it's slowing down for the reader, which can interrupt the flow and even take some readers out of it a little. Some writers prefer to only include a couple of the details they think are most interesting, or say the most about the character/thing being described, which means the story's flow doesn't get broken up and doesn't bog readers down with detail, but also means readers' mental image probably won't match perfectly with what the writer had in mind.
Full disclosure: my style used to be the former, which was a pretty popular style on this forum for awhile. On Serebii, it wasn't uncommon to say "well, maybe whoever is reading my Pokémon fan fic doesn't know exactly what each Pokémon looks like." Since then, I stick more with the latter style, mostly because I have stopped obsessing over being overly-descriptive and prioritized flow of my stories. I also assume that most people reading my fics know Pokémon pretty well, and if they don't know a particular Pokémon, they'll Google it.
All this to say, the current style in Pokémon fan fiction (at least on Serebii) is to go with the latter, and I think it's a general good choice. Even most novels don't spend tons of time describing each character, at least not in a big info-dump all at once. As Negrek pointed out, a great way to go about this is figuring out what details matter the most at that particular moment, and what impression it creates. (You can always add more details later in the story!) For instance, if you want to make a Tyranitar come across as scary, you can describe it as "a hulking beast, glaring with tiny eyes at the creatures huddled below it, shaking the rows of spikes on its back and swinging its spiked tail that could probably smash a tree to splinters." To show how elegant a Mitolic is, you can write "blinking serenely, the sea serpent's pale body undulated slowly on the sand, sunlight glinting off the scales of its multicoloured tail." Adding actions to your description makes it more interesting, and gives a nice sense of life and movement to your characters, even if they're not really doing much!
It's definitely tough to describe certain Pokémon (I always love when a non-Pokémon fan tries to describe a Pokémon based on someone's description alone), but Venia Silente had some great tips! I think you can save yourself a lot of anguish if you don't worry about every detail, but it's up to you!
Also, just to say: it's totally okay to skip around when writing your story! If a certain description or bit of dialogue or whatever is tripping you up, you can always come back to it later! Make some kind of note in the document that this section is missing something, and keep writing while you're still on a roll. Writers' block is a nasty thing, and this is a common way to get trapped by it!
~Psychic