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.