@Angrybirds,
"On the last evening" might have a specific meaning, such as on the last evening of your vacation. In front of "we stayed," you could use the the adverb "where," or the combination "in which." If you use only "which," then the grammar itself is still okay, but the meaning will shift. Think of your sentence as broken up into its clauses and phrases like this:
We liked the hotel (main clause)
where we stayed (adverb clause)
on the last evening (prepositional phrase used adverbially)
Now let's try "which." The words "which we stayed" create an indirect relative clause. It's called "indirect" because the clause's subject, "we," refers to something different than the noun that the relative clause describes: "hotel."
We liked the hotel (main clause)
which we stayed (indirect relative clause)
on the last evening (prepositional phrase used adverbially)
The only thing I see bugging you is the semantics: we rarely "stay a hotel." We do buy hotels, and "We liked the hotel which we bought on the last evening" is a sensible thing to say. Now the next little mystery: English allows nouns of time to be used as adverbs. This is where we have "the last evening" (without that preposition "on"), or if you prefer, "last night." These noun phrases of time can be used like any other adverb. This gives
We liked the hotel (main clause)
which we stayed (indirect relative clause)
last night (noun phrase of time used as adverb)
We're almost done. We don't stay hotels, but we do stay IN hotels. Since the relative clause refers to the hotel, we put this preposition, "in," right in front of the clause: "We liked the hotel in which we stayed last night." Sometimes English will put the preposition at the end of the relative clause instead of before it. That gives "We liked the hotel which we stayed in last night."
That awkwardness in you ear came from "We liked the hotel which we stayed on the last evening," which has ambiguous structure:
We liked the hotel (main clause)
which we stayed (indirect relative clause)
on the last evening (prepositional phrase used adverbially)
or
We liked the hotel (main clause)
which we stayed on (indirect relative clause and its governing preposition)
the last evening (noun of time used as adverb)
The problem then is that we don't usually stay ON hotels, like on the roof or something. On the other hand, we know we don't just STAY them, either. So it sounded funny. The verb "stay" can be used with "on," however, when we have a different noun. We might stay on the corner until the light turns green, for instance. Easy!