As a native English speaker in North America, it does perhaps sound a tad odd, but that's a hard call to make without reading it in context. Several thoughts:

<ul>
<li>if you want to keep the word "way", I would use the infinitive: "way to clean"</li>
<li>if you like "method", I would use "of": "method of cleaning"</li>
<li>the most natural to me, without any other context, is "they taught us how to clean"</li>
</ul>
Edit/response to comment: I emphasize native because I feel it's important to point out I'm not an ELL. If I were responding to a question about another language, I would highlight that I am NOT a native speaker and to take my response with a huge grain of salt, as my ear may not be good.

I'm sorry, I can't give reasons. In my experience, what I said stands. I suspect the things that bother you reflect the difference between our two languages. (Tongue in cheek there, but they really do seem that way.)