Well, that's a complex question :P
There's lots of different kinds of complexity, requiring different tools - a complex character is different than a complex setting; a complicated plot is different from a plot expressing a complicated idea.
Here's some guidelines I can share, from hearsay and from experience. I tend towards SF/F examples; hope these are clear.
Show, Don't Tell: Though this rule of thumb doesn't always hold, it's particularly apt for expressing complexity. Don't say that something is complex. Don't explain in detail how complicated it is, nor how to understand it. Rather, show, in the action, the complexity you're striving for. Demonstrate that the subject is not simple - maybe some characters don't understand it, or clearly struggle with it, or would like to resolve it, or appreciate its many-faced nature. And then, to explain the complex element, show different parts and aspects of it - each alone, and how they cohere into a whole - to let the reader get the sense of how they gradually come to understand the complexity.
Don't Infodump Until The Reader Wants It: And, when you need him to know it, make him want it. Introduce information when it's clear to the reader that this information is interesting and important; not before. "I'll explain the nature of 12th century water pumps, and that will assure that the rest of the story will be entirely clear" makes sense to the author, but if the reader has no obvious incentive to get through the description, he won't. If that detail is truly necessary, the trick is to come up with a good reason that info will be important NOW ("Dad, Dad! Jimmy just fell into a 12th century well!"), and that will give you the reader's interest long enough to get across the information that you need him to have later.
Make The Complexity Central To The Story: Self-explanatory, I should hope. There's no point in being complex just for the heck of it. If the complex element is what the story is about, the reader will naturally be interested in it (assuming you've made him interested in the story), and be willing to devote effort to understanding it.
A good example of this is the honored tradition of science fiction detective stories, like many of Asimov's robot stories. Science fiction introduces new worlds, with imaginary concepts with imaginary rules, that the author might desperately need the reader to understand completely. If the story is an investigation story, why then, the protagonist is exploring the world by his very job description. All he does in the story is explore the world; understand the rules; figure out how everything works. That's a great way to take a lot of details that might not interest the reader - e.g. how the Laws of Robotics work - and make them interesting - e.g. by having a murder investigation hinge on clever manipulations of the Laws. This is also basically what Dan Brown does - it's not an art&history lesson, it's a treasure hunt for a dastardly conspiracy! WE MUST DISCOVER THIS INFORMATION! IT'S REALLY IMPORTANT AND INTERESTING etc.
Build It Up: Complexity takes time. Don't try to get it all across in the first scene (not even by showing!). It'll be tough to cram in all you want, and let's be honest - complexity is something that dawns on you gradually, with time.
George RR Martin's Song of Ice and Fire has a vast cast, byzantine politics, huge world. But he starts out with a very tight focus - a single family, and mostly the children, who don't know much about everything that's going on. From the beginning, he gives lots of hints that things are changing and danger is afoot. Gradually, all kinds of hooks start fleshing out, and more and more threads get time in the spotlight... but never before some buildup to the fact that these threads are interesting, dynamic, important - maybe mysterious and dangerous, even. Nothing comes out of the blue. Complexity shows up only after initial interest have been established.
Similarly, in Dragonlance, lots of readers love Raistlin as a complex character (I know, I know - not exactly great literature... but bear with me). At the beginning, all you see of Raistlin is how bitter and standoffish he behaves, and his brother's love for him. Gradually, his actions show more of who he is, and more of his past is revealed. And note that not very far in at all, a "complex" note is tossed in - with this dark character showing compassion for a lowly, miserable creature. So pretty soon, we know that Raistlin is dark, but also has a more complex nature than just that.
In summary: don't try to convey all the complexity at once; do give clear indication that certain things are complex, incompletely understood, and have interesting secrets to discover later.
Define Clear Questions To Be Explored: Complexity isn't mere richness of detail. It's things being... complicated. Unclear. A really good way to do this is to set up questions about the element. Not only do questions interest the reader - by presenting the element as something complex enough to have questions about, oblique enough that figuring out the element's nature isn't simple, they demonstrate that the element is truly complex, and reinforce the sense of complexity that you're aiming for. Open questions make an element complex, intriguing, and unpredictable.
My tip here is to set up such questions clearly and explicitly - make the reader anticipate the answer before he gets it (if he gets it), rather than giving it to him in the expectation that he will appreciate the added complexity.
House is a great example of this technique. House is a misanthrope, but he's also unpredictable and complex. At any given moment in the series, there are several questions open on House's personality and psyche. What was House like before his leg surgery? What is he willing to do to keep his job, or his team? How much does he care about his patients? We don't just grow to understand him better - the questions are posed first, and then we gradually fill in the answers. And raise new questions, of course.
Complexity Evolves: The longer you spend in a single mileau, the more details and history you build up, even if it begins simply; complexity can easily evolve by continuing to extrapolate past elements into new stories, and playing existing elements off against each other.
A lot of series (TV and books) bank heavily on this - think of the Star Trek universe, of soap operas, of Doonesbury or of Order of the Stick. They start out simple, sometimes even simplistic - but with time, they grow and sprawl, and from their unique configuration of not-terribly-interesting ideas, and from the simple accumulation of time and history, they extrapolate something new and unique. That's why lots of things might "only get good halfway through Season 2" or whatnot - leading some to try to start off directly from mid-Season-2 to begin with. This technique can have its own issues, but it can work very well - skip past the first 10 stories; get to the stuff that can only happen once those stories have happened - making those stories, by necessity, relying on a more complex history, and being more complex themselves.
That's it, I think. Hope these observations are helpful :)