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 the case for two given graphs; 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 neighbors 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 surprisingly difficult (and interesting). 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".