Learn Arabic (Modern Standard): هي وجدت حقيبتها أمس.

The base form of the past tense verb is وجد (he found). To make it feminine for "she found", we add the suffix ـت (-at) to the end. This makes it وجدت (wajadat).

Since the verb already means "she found", is the word هي (she) necessary?

No, it is optional. The verb وجدت alone perfectly translates to "she found." Including هي at the beginning just adds a little emphasis, like saying "She is the one who found her bag."

I know the word for bag is حقيبة, but it looks different in حقيبتها. Why did the spelling change?

The word حقيبة ends with the special feminine letter ة (taa marbuta). You cannot attach another ending directly to this letter. When we add the possessive suffix ـها (her), the tied ة has to "open up" into a regular ت (taa). This creates حقيبتها (her bag).

Can I put the word أمس (yesterday) at the beginning of the sentence instead?

Yes! Time words like أمس are very flexible in Arabic. You can place it at the end, as in this sentence, or at the very beginning without changing the core meaning.