Usually a combination of "brainstorming" and "alien creation rules".
In most cases I have a basic idea for an alien creature and then use rules
like Flynn's Guide to Alien Creation to add some of the details that were
not covered by my concept.
For example, I "knew" that the basic creature archetype of Pandora would
be aquatic with eight limbs - four tentacles with claws and four fins - and
that it would be able to sense electromagnetic fields, sound and vibrations,
but that it would otherwise be blind.
Flynn's Guide then added that it is cold blooded, hermaphroditic, egg-lay-
ing, and a couple of other things I had not thought of.