How do we know that our genetic similarities to other species is actually due to common ancestry?
We don't know, and we never will. Science doesn't work that way. But evolution is the simplest hypothesis that is both falsifiable and consistent with lots of experimental data. Therefore it is the currently accepted scientific theory.

I would agree that genetic similarities between current species does not in itself suggest that they evolved from a common ancestor. But knowing the genome sequence of various species let's you do much more than simply measure pairwise similarity between species. The structure of genetic variation (losses, duplications, inversions, mutations ... ) also fits with evolutionary models. And crucially, genome sequences confirm predictions made by the evolutionary theory --- evolution is not just a post-hoc explanation of data, it has actually been tested many times over, and has never been falsified.

A good example is the sequencing of the human and chimpanzee genomes. We knew long before any genome was sequenced that humans have 23 chromosomes (23 pairs), while chimpanzees have 24. If the theory of evolution is correct and we do have a common ancestor, then that ancestor should have 24 chromosomes, like the chimps do, and it must be that in humans, one chromosome is a fusion of two ancestral chromosomes$^*$. This is a strong, testable prediction: if we don't find this arrangement of chromosomes, then evolution is proven wrong! In the 1980's, the sought fusion chromosome was found using high-resolution cytogenetic banding: it's chromosome 2. Modern genome sequencing later localized the precise fusion point on the human chromosome.

Also, the fossil record provides a timeline, not just a bunch of more or less similar organisms. In general, we don't find old fossils of modern-day animals (including ourselves), but we do find old fossils of species that no longer exist today. And when piecing together the findings, it looks like there is a sequence of gradual changes over time. That's a pretty good clue. What hypothesis might fit this data?

If you are suspicious about the theory of evolution --- which is fine, you should think critically about everything in science! --- then you must look for an alternative hypothesis which is falsifiable and fits the data. (Note that "god made everything" is not a falsifiable hypothesis, since it makes no testable predictions, and therefore not relevant to science.) If you come up with anything, let us know!

$^*$ As pointed out in comments, a priori one could imagine other rearrangements between the ancestor genome and the chimpanzee/human genomes that give the same result, but I believe this is the simplest hypothesis.