Two finite graphs have the same universal cover iff they have a common finite cover. This surprising fact was first proved by Tom Leighton here:

Frank Thomson Leighton, Finite common coverings of graphs. 231-238 1982 33 J. Comb. Theory, Ser. B

I'm quite sure the paper also presents an algorithm for determining if this is really the case; essentially you develop a refined "degree" sequence for the graphs, starting from "# of vertices of degree k" and refining to "# of vertices of degree k with so-and-so vertices of degree l" etc. 

As an aside, the reason this result is so surprising is that it says something highly non-trivial about groups acting on trees (any two subgroups of Aut(T) with a finite quotient are commensurable, up to conjugation), and proving this result directly via group-theoretic methods is highly non-trivial. There's a paper of Bass and Kulkarni which pretty much does just that.

Edit: I just ran a quick search and found this sweet overview: "[On Leighton's Graph Covering Theorem][1]". 


  [1]: http://arxiv.org/abs/0906.2496