We're assuming that you want to write an alien psychology that doesn't match up exactly to the human mind, so we're going to stick closer to the Hard end of the Mohs Scale of Sci-Fi Hardness. It's fine to veer off from it, of course, and your only issue with soft sci-fi may be that you dislike Rubber-Forehead Aliens and there are few writers whose stories have Soft physics and Hard aliens, but if your story is Soft you might want to make it clear to the reader beforehand that your story will have Babyeaters, not Klingons.
- Blue and Orange Morality is pretty much required. Even separate human cultures can get pretty strange, so it would take a lot of improbable coincidences for an alien culture to be easily understandable by the humans that meet them.
- Starfish Aliens, Starfish Language, and similar tropes are also important. You could get away with Humanoid Aliens instead of Starfish Aliens, but don't do this for more than one alien species in a given universe if you don't want to worry about stretching plausibility too far. The other tropes are still necessary for Humanoid Aliens; even human languages possess amazing diversity, so you don't have any excuse for your aliens speaking with the exact same grammar structure as English.
Now here's where we get into the meat of it. Unless you've gotten a psychology doctorate and enough money to live on for the next few years, you probably don't want to design an alien mind from scratch. With that in mind, you probably want to take a short cut to get you started, like rearranging the steps in Maslow's Hierarchy of Needs. For example, we might give them, from most to least fundamental, self-actualization needs, safety needs, physiological needs, esteem needs, and finally love/belonging needs.
Our aliens developed from a highly social species which never really had much need for complex thought thanks to things like heavy r-strategy reproduction and safety in numbers. Sapience was only able to develop among those that rejected the group (or were rejected by it), at least to a point, and had to manage on their own merits, with only the cleverest managing to reproduce. It is perhaps because of this that the need to develop one's "selfness" and personal identity to its maximum potential is more important even than the need for food; I Die Free is very common in this species. The reason for the importance of safety needs over physiological needs is easier to figure out: their environment suffered disasters on such a regular and widespread basis that you couldn't count on having tomorrow what you had today. More important than getting a meal was making sure that you wouldn't lose it once you got it, and this is reflected in extreme caution and commonly a refusal to acquire anything, whether it is food or a house, without some way of keeping it safe. Insurance companies would love this species. Because of their individual-centered origins society is a lot harsher than usual, and while the aliens gather in groups to accomplish tasks that they couldn't accomplish on their own (civilization does a lot of good when it comes to keeping your stuff safe), they're not particularly thrilled with each other. If you want to get along then you need to be able to respect the other person, and the current civilization is descended from the aliens who felt a strong need to earn that respect. Love/belonging needs are very light and few, and in fact a fair number of the members of this species lack them entirely without being labeled insane.
Don't forget that you should give your aliens a few strange behaviors which simply don't help. Human psychology is full of things like confirmation bias, and aliens will likely have their own oddities.
- Rubber-Forehead Aliens should be avoided. If you must, Humanoid Aliens is acceptable, but if you're going to go to all the trouble of creating a genuinely alien mind then you should go a few extra feet and not just slap some make-up on your aliens. A separate "So You Want To" article now exists to deal with the physiological end of the alien-building chore, titled Create Believable Aliens.
- Aliens should have individual personalities, and not come from a Planet of Hats. On the other hand, they should still have similarities which bind them together just as two humans would.
- On that note, be VERY careful if you insist on making Scary Dogmatic Aliens, otherwise don't do it. It can be easy to start doing The War on Straw or Malicious Slander (two tropes that should be avoided at all costs), especially if you're writing about groups, ideologies and/or beliefs you dislike. While some things are wrong and need to be called out (for example, racism), there are others where the matter is very complex and the target may be better than perceived so it's wrong to single them out for scorn (for example, certain religions). At the very least, do some research and be honest about whoever you're focusing on if you use Scary Dogmatic Aliens.
- While ordinarily first contact would send your protagonists' minds reeling (and likely the aliens' too- remember that they're probably going to have as much trouble with us as we will with them), and it will definitely do so for your readers, what if the protagonists are from one of those aforementioned ridiculously strange (to most humans, anyway) cultures, and said culture is actually pretty close to the alien culture that they came in contact with?
- Communication, while difficult in the 'very' beginning, is helped along by the fact that at least one of the two parties has designed a language designed to be as unambigious, logical, and straightforward as possible. Think a sort of super-Logban with healthy doses of mathematics and several rephrasings of each statement just in case the other guys are using a different logic system than you are.
- The aliens come from a Planet of Hats but in this case it's justified, thanks to genetic engineering. Let's say that it becomes feasible for individuals on their world to genetically modify the behavior of their children, and many who do so will make it instinctive for them to possess certain traits which are seen as desirable in that culture (if you're a Klingon, why not make 'sure' that your kid won't bring dishonor to himself or the family by totally removing the "or flight" half of the fight or flight response?). Because these desirable traits come more easily to them, they're seen as more attractive to other aliens and they may also be genuinely more successful depending on what traits are ingrained. This will not only ensure their reproductive success, which will on these traits to the next generation, but encourage others to give their own children the same modifications so that those children can keep up.
- Similar to the above, while there were difficulties in the past, humans and aliens have since modified themselves to share particular psychological traits. The original humans and aliens would find either group hard to understand (and vice versa, for that matter), but the new humans and aliens are far from hopelessly confused by each other.
- A representative of an art gallery must figure out how to communicate with an alien artist, figure out what ownership and property mean in the alien's culture, and convince the alien to let the art gallery have some of its pieces under the ownership terms of either human or alien culture. After all, True Art Is Incomprehensible.
- A human cleric/missionary seeks to evangelize an alien for a human religion (or vica versa). Besides figuring out how to get the concepts across, explain the cosmology and theology, missionaries will need to think on their feet (especially if FTL communication isn't possible and the leadership of the church isn't in that star system) in order to solve doctrinal questions like what to do when a Catholic alien wants to be a priest but, while currently male, will transition into a female state later in life.
- A human raises an alien from infancy and teaches it human values and what is known of the aliens' language, but this doesn't go perfectly because of the fundamental differences in human and alien psychologies.
- Robert Freitas' Xenology, which is a comprehensive look at some of the possibilities for everything from alien physiology to moral systems.
- The vampires and scramblers Peter Watts' Blindsight.
- Three Worlds Collide, which has the Babyeaters and Superhappies.
- Just about any alien species created by Larry Niven. He's practically made a career out of forging believable alien psychologies, from the cowardice-is-a-virtue Puppeteers to the hyperspecialized Moties to the three-life-stage Pak to the herd elephants of Footfall.
- Be sure to take a look at the entries in Starfish Aliens. I've only included examples here that you can read online.