This question arose from the responses to this question. The references to the comments of Karl Schwede and VA are to comments made there.
The blow-up of the variety $X=\mathbb{A}^2$ along the closed subscheme $Z$ defined by $(x,y)^2$ is non-singular. As Karl Schwede points out, this example is trivial in the sense that the blow-up along the power of a maximal ideal is naturally isomorphic to the blow-up of the maximal ideal. VA's comment, on the other hand, suggests that perhaps singular closed schemes $Z$ with $\operatorname{Bl}_{Z}(X)$ non-singular are ubiquitous.
This suggests a question: what are non-trivial examples of a singular closed subscheme $Z$ of a non-singular variety $X$ with $\operatorname{Bl}_{Z}(X)$ non-singular. Here "non-trivial" means the ideal of $Z$ is not a power of the ideal of a non-singular subvariety.
Particularly interesting would be such a $Z$ such that
$\operatorname{Bl}_{Z}(X)$
is not isomorphic (as a scheme over $X$) to $\operatorname{Bl}_{Z'}(X)$ for any non-singular subvariety $Z'$ of $X$.
Edit: I have not been able to access the paper "On the smoothness of blow-ups" (MR1446135, by O'Carroll and Valla) yet, but the mathsci review states that they prove that the blow-up of a regular local ring $A$ along an ideal generated by a subset of a regular system of parameters is smooth. Let's also consider those examples to be trivial.
Edit: I added "of a non-singular variety" to the title to emphasize that I am interested in examples where the ambient space is non-singular.
Best Answer
Suppose that $X = \mathbb{A}^2$. Let $Y$ be the blow up of $X$ at the maximal ideal $(x,y)$ and let $W$ be the blow up of $Y$ at a point on the exceptional divisor of $Y$ over $X$. Of course, the composition $f: W \rightarrow X$ is birational and an isomorphism away from the origin. The fiber of $f$ over the origin is the union of two $\mathbb{P}^1$'s meeting at a single point, but the total space $W$ is non-singular. The map $f$ is identified with the blowup of $X$ along some closed subscheme $Z$ of $X$ supported only at the origin. I believe an example of an ideal defining such a $Z$ is $(x^3, xy, y^2)$.
By taking the composition of blowups along smooth centers, there is some ideal sheaf on the base giving the composition in "one step". In theory, you can compute this ideal by tracing through the proof that every birational morphisms is a blow up - but in practice I think this is usually difficult.