There's something very mysterious, and often quite appealing, about having a character who thinks differently from other people. You might have a bad guy who's insane, or a character whose different way of thinking makes it hard to know whose side he/she is on, or you could have a protagonist whose voice you want to make really different.
So, what do you do?
I recommend diving in right away, and exploring the character - the parameters of their different concerns, their behaviors, etc. That's an important first step, because you'll very likely have excellent instincts about what kind of behavior and thinking would best fit into your story as a whole. However, once you've got the basics of their thinking and behavior sketched out, the next step I recommend is looking around to find out what exactly is going on with your character's thinking.
When I first created my antagonistic character, Nekantor, he was power-hungry and mean, paranoid, and was never satisfied with the performance of his servants. The problem was, he came across as stereotypically bad, and I couldn't really make any of his behaviors extreme without having it look like I was working too hard as an author. Then I realized that his paranoia could be part of an actual mental disorder, and after some looking around, I found the perfect one for him: obsessive-compulsive disorder. A person with this disorder will have repeated anxious thoughts surrounding a particular fear - such as a fear of germs, or a fear that their parents will die, or a fear of Colorado (seriously). Those thoughts will then give rise to ritual behaviors intended to relieve the anxiety. Nekantor is obsessed with control, and in particular, he fears things getting out of the placements (literal or figurative) that he has put them in. This allows him to be much more extreme in his behaviors (like checking rituals), but also makes him more vulnerable and believable as a character. It applies not only to his servants' performance and the arrangement of his rooms, but to people behaving appropriately for their caste, and to people trying to keep Nekantor from controlling their business. It gives rise (in part) to his paranoia. If he were cured of it, would he still be a bad guy? Oh, yes. But he wouldn't be nearly as interesting.
Anxiety disorders are extremely interesting, and can add dimension to almost any kind of character, even if you decide only to use them in a mild and non-pathological form. Take Indiana Jones and his fear of snakes, for example. I highly recommend this site at the National Institute of Mental Health (NIMH) which can provide you with a basic introduction to the features of several different anxiety disorders. One of the most interesting things here, to my mind, was that each entry has a statement from a former sufferer of the disorder about how it felt when they were at their most anxious. If you're planning to write from the point of view of someone who has an anxiety disorder, this is very useful stuff.
You may have heard of the book, The Curious Incident of the Dog in the Night-Time, whose point of view protagonist has Asperger's syndrome. Here is the NIMH site dealing with Autism Spectrum disorders, of which Asperger's is listed as one mild form. You may also be interested to learn about Temple Grandin, who has used her different way of thinking to help her be a unique resource in animal management. Here is a fantastic video of her talking about different kinds of minds and the unique resource they are.
You may also be interested to learn about bipolar disorder, schizophrenia, depression, or eating disorders (all these are the NIMH links).
When this is well done, it's incredibly compelling. It also requires a great deal of research to be done well. I encourage you to look through the NIMH links, which I've found to be very informative. Do also see what you can find of real examples - either contacts of your own, or videos, etc. Find as much information as you can to make your character portrayal ring true.
There's also a lot of room for individuality in the way you treat a character, obviously. When I work with Nekantor I try to make his narrative reflect his obsessive tendencies by having him think repetitively and be very judgmental, in addition to having him engage in compulsive behaviors. When I work with my character the History Keeper, I try to keep her subtle, even though she's delusional and has an unusual condition called hypergraphia (she can't stop writing).
I hope you find this post gives you some resources to strengthen your unusually-thinking characters, by grounding yourself in research on actual mental disorders.