This seems like a simple question, but I cannot find a clear answer. The book of Genesis (1:29,30), implies that Adam just ate "plants and herbs". So I think it is safe to assume animals were not eaten? Now if animals did die, my question would be "why"?
The views of Christians on this matter can basically be divided into two.
A key passage here is Romans 5:12-21, which says:
Young Earth Creationists - before Adam sinned, nothing died
In the literalist view, the interpretation of the passage above is that Death is punishment for sin, and nature as subservient to mankind shares in Adam's fall. Therefore all death, even of animals, is a result of sin, and did not occur until Adam sinned.
This passage is used as one of the chief Biblical arguments that Genesis 1 should be taken literally and not metaphorically. If there were indeed millions of years of evolution before Adam, then these could not have happened without death and this passage would be contradicted.
As you already stated, Adam and Eve were vegetarians, so there was no need for there to be animal death in order for them to eat. (In fact it is not until Noah that humans are allowed to eat animals).
Other Christians - Physical death of animals did in fact happen before the fall
If you do not hold to the Young Earth beliefs then it is clear that death of animals must have occurred before the fall. The interpretation of the Romans 5 passage is that it is about only the death of humans - death for animals is entirely natural and not the result of sin. (The NIV quoted above takes this line in its translation, but not all translations do). Some also take it to mean 'spiritual death' - i.e. that humans were always destined for a physical death, but that people would know that they were destined to pass on after death to be with God, and it would be entirely natural and nothing to be afraid of. After the fall humans would also suffer spiritual death, i.e. eternal separation from God. The Bible does elsewhere use the word 'death' to refer to spiritual death and not physical death.
If you hold that the Fall is metaphorical rather than literal then it isn't an issue.