I dislike the fact that people use h3 rather h1, or skip a level just because of the way it looks. IMHO, headings signify document structure, rather than layout. The layout is just a side effect, customizable through themes.
Having "wrong" heading levels also makes it more difficult to generate proper TOCs and/or export to other formats.
While wiki gardening, is it acceptable to completely restructure other people's pages to use proper nested heading levels?
Yes, it is acceptable to restructure peoples' headers to following the site's established or de-fact standards.
When you edit someone's post, the community will decide if your edit was deserving or superficial by either rolling back your changes, keeping your changes, or editing your changes.
See the Wikipedia Manual of Style
The good thing about wikis is that you are free to edit it! if you think restructuring it makes it better, then by all means do it.
It depends what the coding/layout guidelines state. If they say to use h3 when they have used h2 then you could edit it. However, if you are editing someone else's post based solely on your personal preferences then I would say that's wrong.
Aside from that, you can always ask the author if you can find them.
I agree with Teifion. It depends on the individual wiki's guidelines and/or rules, but also the rules of conduct. On some sites it's ok to edit whatever page you want, on some sites it is considered best to notify the original (or maintaining) author.
The other thing that I'd say is that it would be more courteous to present your arguments to the initial page author, or most recent maintaining author. You could also add a comment on the discussion page stating your opinion. Because while it is generally considered good style to use H1 first then H2 based on content level and not skip, it really is a matter of personal preference.
As others have mentioned, it's best to start a conversation on the discussion page for the article if what you're doing is a major over-haul. If someone has one H1 and two H3s in a fairly short article, I don't think it's a big deal to change those. When in doubt start a discussion.
Another thing that might be pertinent is, if you can't find editing or style guidelines regarding use of headers, their effect on the table of contents for an article, the styles used to control their appearance, etc then you could always start discussion about that. If there is disagreement about what is the correct layout for an article, then the wiki will be really hard to read. Whatever is decided by such a discussion (make sure to get consensus and quorum or whatever's appropriate for wiki-spanning decisions on the wiki in question) can more assuredly be unilaterally edited into any article not conforming.