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:
- if you want to keep the word "way", I would use the infinitive: "way to clean"
- if you like "method", I would use "of": "method of cleaning"
- the most natural to me, without any other context, is "they taught us how to clean"
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.)