Let's assume that there exists other intelligent life somewhere in the Universe. I like to consider the various parameters of the properties of such a life, which would define commonalities between us and them (it), which would help define how we could communicate.
Unsurprisingly, as any topic that tickles our (I'll argue evolutionary!) desire to explore, there has been a lot of thought put into this problem. I'll do what I do best -- start with some of the context I've acquired over the years (the Pioneer message, the Arecibo message, a much longer one, or Carl Sagan's Contact) to see where I can take the idea (a good test of how I'm thinking about it, and possibly a way to think outside the box), and would love to hear from those who know more, or have thought about it, especially if you have differing opinions.
Let's start with a relatively simple model. An alien race that is based on similar biological mechanisms, thus consisting of individuals that have become intelligent through evolution, that have acquired inter-generational (institutional) memory and thus civilization through some method of communication between individuals. Note that I'm not necessarily assuming many of the aspects of such a life -- language (imagine a species that can communicate through some form of telepathy), physical attributes (such a life may be non-carbon based and interact with the environment in wildly different ways than we -- for example, be entirely gaseous and receive and generate arbitrary signals along a specific range of electromagnetic spectrum), motivations. Let's assume, however, that the Universe behaves the same way locally to this alien life form as it does in our environment.
The most interesting aspect in such a case is the mode of communication. What can we assume is common? Nothing physical, for sure. For species that travel in the electromagnetic spectrum (just like light does), our highways and staircases and in general attraction to solid state objects would make very little sense. Instead of trying to start with something most concrete to us, it makes sense to start as broadly as possible. We need a medium and a message.
For the medium, we could use the electromagnetic spectrum. Really, anything we can generate that can travel far, fast, and be distinguishable from everything around us. Don't be fooled by visible light! -- although it's possible that there is some cosmic law that makes visible light frequencies be a local maximum along some dimension -- the energy required to receive it relative to its usefulness in the surrounding environment (seeing X-rays instead of "visible" light would not be all that helpful to early humans) -- this is highly dependent on the initial conditions of life. Or maybe it's a fluke. More generally, anything that generates a force field, though it's harder to generate ripples in the gravitational field as easily as it is to blast electromagnetic messages. Quantum effects are likely too small to be noticed, although I don't really know anymore, given all these spooky things happening.
The message? Non-random (non-chaotic), but not too regular (pulsars send out regular messages out in the space). Taking both together, it's a pretty natural thing to mimic the universe around us -- assuming that what we observe of distant stars from Earth, the aliens can also observe from their vantage point -- but provide patterns whose complexity is a tad higher than the complexity of similar messages generated by the Universe itself. Prime numbers are good candidates -- and in general, anything that is really fundamental and to do with mathematics, because it's very likely that an alien race knows mathematics (as the study of patterns, totally abstracted from the source of these patterns). Unitless quantities are better than something with an intrinsic measure, because the fewer assumptions, the better.
Can an alien race be sophisticated enough to be able to receive our communication, and interesting enough to talk to, but not understand at least some form of mathematics? Could an alien special have developed (not been born with!) interstellar travel and not understood binary systems. Science fiction scenarios aside (an alien species is decimated along with its cultural heritage and ends up traveling across solar systems without the knowledge of how its machines take it thus far), I think there is universal consensus that the answer is no. And in fact, an ability to think abstractly is very likely a sign of intelligence. But this does not hold the other way -- I can imagine a race that is either so sophisticated as to think of mathematics the same way we think about the pulses of Nature and simply ignore any such signal, or so intuitive that they don't identify mathematics as a discipline. For the former, introducing some obvious and non-obvious error in the message might be a great solution. A race that can enumerate prime numbers is intelligent, but a race that makes a mistake early on must be much more street smart!
But even assuming an alien race does understand the concept of binary arithmetic, it may not be able to understand its encoding. Would a series of dots and dashes in a column corresponding to the numerals necessarily be informational? Not if the aliens don't have spacial awareness. Would a series of beeps be a good encoding? Not if the aliens can't hear or -- more interestingly -- don't have a notion of time (or cause-and-effect).
Math aside, the fundamental laws of the Universe would probably be a common base, although one can imagine a less curious (or much more sophisticated and thus thinking of the laws of the Universe as irrelevant) life form, or a more precise one where our crude approximations of the Universe map to something incomprehensible to them. We can ask astronomy what quantities are pervasive and communicate their ratios. This is what Pioneer and the Arecibo messages were, and it is a great way to communicate our relative knowledge of the universe with the above assumptions in mind.
There are alternatives to this model that would work similarly in some aspects. Consider a species that is a single individual (instead of many individuals that communicate with one another and thus pass the knowledge). Such an individual may not comprehend the notion of individuality, but may still be able to communicate with us the same way, definitely remotely, where we can approximate mankind as a single individual, at least in the beginning of the dialogue. If their Universe doesn't behave the same way as ours does (say, the speed of light, due to some quirkiness, is infinite in some valley of the Universe), if the alien race can perceive the different laws elsewhere, they can still compare our crazy patterns of high entropy to the surrounding comparative dead silence. Though such an alien race may not be particularly useful to talk with (if they have no insight that can be understood by us).
The concept of communicating with an alien race is a fascinating one. Clearly, there is no way to think about it in the most abstract way -- there are always assumptions that we must accept. Let's hope that we'll get to tackle this problem at some point in the near future, and let's hope that we get some of our assumptions right -- we wouldn't want to miss an alien race that happens to be intelligent in a different way. Or be trampled by one in search of intelligent life.