You can (write a program to) form the graph Laplacian (for n reasonably small) and use the matrix-tree theorem to get the number of spanning trees. See

http://en.wikipedia.org/wiki/Kirchhoff%27s_theorem

The triangular grid is a bit trickier to handle both on paper or on a computer; you may find techniques for the graded lexicographic index described at

http://blog.eqnets.com/2009/10/06/a-graded-lexicographic-index-part-1/

and subsequent posts helpful in dealing with the triangular lattice.

**EDIT: The answer is at http://www.research.att.com/~njas/sequences/A007341.**