This is actually a major question in SETI study today.
First off, I want to cut down one of your words: "How could we guarantee that these aliens would recognize our signals..." we cannot guarantee anything. Current prevailing linguistics opinions indicate that it is impossible to guarantee another mind recognizes anything at all. The best we can do is give our best effort.
One thing we have looked towards is how we can make a signal look as unlike any known physical sources as possible. Clearly outputting spectra that line up with our sun's emissions is not going to get a message across. We look for things we can do that are unusual.
One of these things we can do is send a very narrow band signal. Most physical sources generate very broadband spectra because they are not actively trying to tune it (with an exception of spectral lines, which end up being tuned to the atoms themselves). There is a standing theory that one of the best ways to send this signal is a narrow band signal focused around a particular frequency at which interstellar hydrogen is unusually transparent. We cannot think of any reason why a natural process would select this frequency, so any signal on that frequency is a solid sign that something unusual put it there.
Another key trick is to keep the bandwidth of the message down and use "simple" modulation schemes. We can transmit data much more efficiently using things like CDMA and QAM, but those modulation schemes look like noise unless you know the decoder ring (in fact, their noise-like appearance is something they designed towards to minimize interference issues). Simple AM modulation is the most likely bet, or perhaps simple FM modulation.
The lower the bandwidth of the message, the more our signal can look like a simple carrier wave at first glance (and thus is less likely to be lost in the noise when alien SETI is looking at many gigahertz of bandwidth). We should keep the message simple. So far, we believe a mathematical message is the simplest. A simple encoding of prime numbers is a popular way to send that message. We know of no natural processes which cause prime numbers to appear, so a signal which counts 2, 3, 5, 7, 11, 13... would look tremendously unusual to anyone listening. Other sequences like Fibonacci have been suggested as well.
High quality repetition is also helpful. There are not many things in nature which send reliable messages with low jitter. We look at pulsars and quasars because they are unusual exceptions to the rule, so there's a good chance the other species is looking for them too. If we can demonstrate a message which is repeated to a tremendous precision (1ppm or something similar), it means the more they look at the message, the more unusual its timing will appear.
There has been discussion of harmonics as well. There has been interest in possible sending the "root" of a chord on the hydrogen line, along with a third and a fifth. This one has been debated (it isn't clear if thirds and fifths are a human thing, or a natural law), but it is out there.