N unlabelled balls in M labeled buckets

So the question is how many ways are there to put N unlabelled balls in M labeled buckets.

One way (I think) I figured it out is $M^N$ ways to put each ball, divided by $N!$ permutations of ball ordering we don't care about:

$$M^N \over N!$$

First, is this correct?

Second, is there another way to approach it without using division? I need to calculate it in a non-prime modulo space so division isn't available. I really need a recurrence.

No, that expression isn’t correct. The correct expression is

$$\binom{N+M-1}{M-1}=\binom{N+M-1}N=\frac{(N+M-1)!}{N!(M-1)!}\;;$$

this formula is derived here. As André notes in the comments, this can be calculated without division, by using the identity

$$\binom{n}m=\binom{n-1}m+\binom{n-1}{m-1}$$

with the initial conditions $\binom{n}0=1$ for all integers $n\ge 0$ and $\binom0m=0$ for all integers $m>0$.

Added: To see why your reasoning doesn’t work, consider the case of $3$ balls and $2$ buckets, labelled $A$ and $B$. Suppose that we put the balls into the buckets one at a time; then the $2^3=8$ possibilities are $AAA,AAB,ABA,ABB,BAA,BAB,BBA$, and $BBB$. One of these puts $3$ balls in $A$ and none in $B$; $3$ of them put $2$ balls in $A$ and $1$ in $B$; $3$ of them put $1$ in $A$ and $2$ in $B$; and $1$ of them puts all $3$ balls in $B$. In other words, the number of permutations corresponding to each distribution of the unlabelled balls is not constant: it depends on the distribution. Here the count of $2^3$ sequences counts two of the possible distributions correctly, but it overcounts the other two by a factor of $3$. And this variation only gets worse as the numbers of balls and buckets go up.

The Stars and Bars approach given in the answer by Brian M. Scott can be carried out without division. For example, Pascal's Identity $$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$$ can be used as a recurrence to calculate the required binomial coefficient. For large numbers, the procedure is unfortunately quite inefficient: simple operations, but too many of them.

There is a substantial literature about methods for computing binomial coefficients. For example, Granville gives a sophisticated method or computing binomial coefficents modulo a prime power.