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.oeis.org/A007341.
