Learn Russian: Откуда у тебя этот пистолет?

In Russian, it is much more natural to express "Where did you get X?" by asking "Where from do you have X?" (Откуда у тебя X?). While you could use a verb like взял (took/got) or достал (managed to get), this verbless construction is the standard, idiomatic way to ask this question in everyday speech.

Could I use Где instead of Откуда here?

No, because it changes the meaning completely. Где asks about static location. If you ask Где у тебя пистолет?, you are asking "Where on you is the pistol?" (like in a pocket or holster). Since you want to know the origin of the gun, you must use Откуда (where from).

Since there is no verb, how do we know it translates to the past tense "did you get"?

The Russian sentence is actually in the present tense: "Where from do you have this pistol?" English prefers to focus on the past action of acquiring the item ("did you get"), while Russian focuses on the present state of possession and simply asks for its origin (откуда).

Does the word order matter here? Could I say Откуда этот пистолет у тебя?

You can, but it shifts the emphasis. In Russian, the most stressed piece of new information usually goes at the end. Откуда у тебя этот пистолет? puts the focus on the gun ("Where did you get this pistol?"). Moving у тебя to the end emphasizes the person ("Where did you get this pistol?").