How would one go about describing a non-human character? I'm not really talking about how to go about the description itself, but how to set it up so you're not just throwing these body parts at the reader. I normally don't have any character description, so I'm having a lot of trouble with this considering the reader would probably like to know something.
(I'm going to use "alien" instead of "non-human character" in this post because it's shorter and I figure that's what you're looking to write about, FYI.)
Like Astinus said, it's really the same thing as describing a human character. You're never going to be able to recreate a perfectly-accurate picture of whatever species in your readers' heads, so instead you have to figure out what's really important for them to know/understand and make sure that in particular gets across. The best way to do this is to think seriously about how your aliens' differences affect how they interact with the world and make sure those differences are apparent in the actual narrative. For example, say your aliens have six arms. If you want your readers to remember that, then it should be consistently relevant to the story, i.e. your six-armed aliens should be doing things with their extra arms all the time, things that it wouldn't make sense for a two-armed human to be able to do. Otherwise, you can mention the six arms for another reason (see below), but you shouldn't count too much on it being informative to the readers--they're liable to forget.
Something else to consider is what you want the readers' impression of the aliens to be. Do you want them to seem intimidating or friendly? Wise or warlike? Something else altogether? Part of what you want your description to do is evoke particular associations for your readers, so they get a sense of what to expect from your aliens even after a brief introduction (you can go on to subvert that first impression later, of course). For example, if you want your aliens to come across as fierce and imposing, the details you'd want to mention would be along the lines of their great height, nasty claws/fangs/spikes/whatever, or elements that attest to their strangeness/alienness that makes them seem unknowable and unfriendly. On the other hand, for an alien you wanted to make seem friendly or welcoming, you'd want to focus on attributes that we generally associate with agreeability or cuteness, like fluffy fur or colorful feathers or features someone would find ridiculous in a non-threatening way. In these cases you're writing to convey the impression of the creature to the readers, more than the literal details of its appearance. If a creature's flouncy fur ruff is only mentioned this once, the readers probably won't remember it, but they will pick up an image that captures some of that ridiculousness and carry it through the rest of the story unless something comes up later to contradict it.
The description you choose for a creature can also indicate something about the narrator if you're using some sort of limited perspective. The details a person notice say at least as much about them as they do about whatever the POV character's looking at. Someone who's had poor experiences with aliens in the past, for example, might be looking for signs of danger in a new species they're encountering or considering how they might defend themselves from it if it attacks. On the other hand, someone with a scientific bent might be trying to make sense of all its weird adaptations and guess what it says about the creature's environment and/or culture. This sort of thing is especially important when the character's attitude towards or opinion of a new species doesn't match up with the actual facts; you want to make sure that you've got both the color of the character's misunderstanding or biases in there
and some hints as to what's really up, too.
Finally, it's very important to be aware of what makes your aliens
different and
interesting. These are the aspects you'll want to focus on the most. If you mention that an alien is "insectoid," for example, people will already conjure up a general image of what you mean: something with a carapace, probably, likely with antennae or mandibles of some sort, and it's usually assumed to be bipedal if it's sapient. Therefore, you don't want to focus your description on what the reader already knows about (the fact that it has a carapace, say), but rather on what's novel about those familiar aspects--say antennae that are rubbed together to make the musical noises that represent the creature's speech--or on elements that are outside readers' usual expectations, such as hypnotic eye patterns on the undersides of the creature's wing cases. Basically, don't spend time on aspects that the reader is going to take for granted; even just mentioning that something is "insect-like" buys you a whole lot of assumptions on the readers' part.
Generally, getting across the literal physical appearance of a creature is probably the least important function of the description you use; writing isn't a visual medium and simply doesn't do that very well. It's more a question of what role you want that species to play in your story and what details you choose to get that across.