In addition to naruto's answer, I'd like to point out that the relative clause "that" that's used in English (even in this very sentence) doesn't exist in Japanese, simply because the structure of the language is different.
It might be easier to explain using examples.
Let's look at your sample sentence in English.
I saw the cow that ate vegetables at the shop.
(I assume here that you mean you saw the cow ... at the shop, and not that the cow ... ate vegetables at the shop.)
Here, the phrase that ate the vegetables describes something about the cow. If we rephrase this as an independent statement, the cow ate vegetables. Translated to Japanese, 牛【うし】は野菜【やさい】を食【た】べた.
If we want to say something else about the cow, and use the vegetable eating as a description of the cow, in English we turn it into a relative clause, and use that "that" to connect the clause to the noun.
In Japanese, however, we don't need the "that". Verbs and verb phrases can directly modify nouns, so we just stick the whole verb phrase in front of the noun.
So if we want to turn the independent statement,
牛【うし】は野菜【やさい】を食【た】べた
... into a relative clause in Japanese, we get:
野菜【やさい】を食【た】べた牛【うし】
Literally, the vegetables-ate cow.
For your simpler sentence, you're just saying:
I saw the cow ... at the store.
店【みせ】で...牛【うし】を見【み】た。
To add our clause to describe more about the cow, we just add that in at the ... Again, English requires the "that", but Japanese doesn't:
I saw the cow that ate vegetables at the store.
店【みせ】で野菜【やさい】を食【た】べた牛【うし】を見【み】た。