Learn Russian: Возможно, он дома.

While here возможно is used as an introductory word meaning "perhaps", it is originally a predicative adverb meaning "it is possible". To say "it was possible" or "it will be possible", you would apply this lesson's rules and add neuter verbs: было возможно or будет возможно.

If I want to say "Perhaps he was at home", do I change возможно to было возможно?

No. When возможно is used to mean "perhaps", it acts as a fixed introductory word and never changes. You only change the main part of the sentence by adding the past tense of "to be". "Perhaps he was at home" is Возможно, он был дома.

Why is it дома and not в доме?

Дома is a special adverb that simply means "at home" (the general concept of being at your place). If you say в доме, it literally means physically "inside the house" (for example, as opposed to being out in the yard).

Why is there a comma after Возможно?

In Russian, introductory words that show your attitude or level of certainty about a statement—like возможно (perhaps) or конечно (of course)—must be separated from the rest of the sentence with a comma.