are "non-parametric" methods well-defined? I have trouble understanding the delineation of "non-parametric" methods. It seems to me most non-parametric methods are parametric, just on a different space than the "standard ones". 
Graph-based inferences are often described as non-parametric, but graphs are fully described by the set of adjacency matrix parameter values. Likewise rankings can be considered a transformation of values onto a different parameter space. Non-parametric seems to get tossed around whenever something is parametric in a high dimensional way on a space we don't typically use.
If the definition is a question of the use of a distribution, coming from a Bayesian background, I guess my intuition is often that usually when we don't put a distribution on something we're often neglecting to capture its uncertainty, rather than something intrinsic to the method. 
Hence there seem to be bayesian formulations of "non-parametric" methods which involve parameter distributions, suggesting that a lack of a distribution isn't inherent to the representation or method, but more of a modeling decision.
 A: Frequentists understand that non-parametric methods entail non-parametric distributions, and use these (or approximations to them) in inference.
I think "I guess my intuition is often that usually when we don't put a distribution on something we're often neglecting to capture its uncertainty" is interesting. My take on the use of non-parametric methods is that they are generalizing from more strict (More certain? What do you mean by "uncertain"?) inferences about the processes driving sample distributions. For example, in inferring differences in paired data, we might like to compare mean differences (paired t test), but if we cannot ascribe normality to the sample distribution of mean differences, we might instead settle for a more general statement than mean difference, and make inference about the stochastic dominance of one group versus another instead (sign test or signed-rank test).
So we haven't describe the continuous distribution driving our continuous data, and instead sacrificed greater discrimination for more generally applicable inference based on distributions of ranks.
A: The short answer is yes: nonparametric statistical methods allow the data to determine the complexity of the model.
Frequentists (usually) do this by not completely specifying the likelihood function, and Bayesians do this through expanding the prior with infinitely many parameters. Here is a not so gentle comparison of the two from a Bayesian perspective while trying to answer basically your question. I highly recommend reading it to get a better theoretical notion. The whole class series of presentations might interest you.
