Which one is correct?
Who are you staying with
Whom are you staying with?
There are not many words in English that clearly tell us nominative or objective case. The pairs he/him and she/her are in the nominative / objective case, and may be used to tell us the answer to your question.
First, one could switch the question around and make it a statement.
You are staying with who/whom.
Then swap in he/him for the who/whom.
You are staying with ?he / him.
(EDIT: The ? notation used on this forum and https://linguistics.stackexchange.com/ indicates questionable usage. A stronger form would be to use *he to indicate that the usage of he is incorrect.)
I suspect it sounds better to most ears to say "You are staying with him," because we use "him" (objective case) with a preposition.
Then swap back the who / whom.
You are staying with ?who / whom.
And then finally back to your original question.
With whom are you staying? or Whom are you staying with?
Grammatically, you need a whom in your question.
But as you can see in the linked question What’s the rule for using “who” and “whom” correctly?, whom may have a stilted or formal feel.
So I'd soften the answer a bit, and say that if you were answering on an English test, use the grammatically correct whom. But if you were asking someone in an everyday situation, use the less formal who.