As Gerhard Paseman mentions, this may be as hard as enumerating all graphs.  If that is indeed the case, you may want to check out this [paper](http://www.tau.ac.il/~nogaa/PDFS/ayz4.pdf) by Alon, Yuster and Zwick.  In it, they mention that given a graph $G=(V,E)$, it is easy to count the number of triangles in $G$ in $O(V^\omega)$-time, where $\omega<2.376$ is the exponent of matrix multiplication.  They generalize this by presenting an $O(V^\omega)$ algorithm for counting the number of $k$-cycles in a graph for $k \leq 7$.  An elegant technique in this area is the so-called *colour-coding* method.  

**Edit 1.** A partial answer to unknown's question is that, $k \in T_n$ for all $k \leq n^{3/2}$ ($n$ large).  To see this choose $j$ maximal such that $\binom{j}{3} \leq k$.  By making a clique on $j$ vertices, and then taking a disjoint union of triangles on the remaining vertices, we can make a graph with exactly $k$ triangles provided $k-\binom{j}{3} \leq \frac{n-j}{3}$.  After some number crunching, this is possible provided $k \leq n^{3/2}$.

**Edit 2.** Here is a some information for $k$ which are *not* in $T_n$.  As Gerhard mentions, removing an edge from $K_n$ destroys exactly $n-2$ triangles.  Thus, $\binom{n}{3} - t \notin T_n$ for all $t=1, \dots, n-3$.  The next triangle-densest graph is obtained by removing two incident edges, which destroys $2n-5$ triangles.  Thus, $\binom{n}{3} - t \notin T_n$, for $t=n-1, n, \dots, 2n-6$.  The next two densest triangle-densest graph are obtained by removing a matching of size 2, which destroys $2n-4$ triangles, or the edges of a triangle, which destroys $3n-8$ triangles.  Thus, $\binom{n}{3}-t \notin T_n$ for $t=2n-3, 2n-2, \dots, 3n-9$.