No because Android's and Linux's security scheme is impenetrable as long as you don't give Root Access or Permissions. Without root, a malicious program cannot take over your system's integrity (there is very little zero day exploit in Linux/Android). And without Permissions, malicious program cannot risk your privacy, e.g. personal data, hardware that can risk your personal data (e.g. camera, mic), location, internet, SD card, etc.
However, Yes because nobody pays attention to those permissions and security warnings. Also, Android can still be a vector for Windows' viruses, even though the Android itself will not be affected by Windows' virus.
The Geinimi trojan that Matt pointed out relies on the program convincing the user to went through the standard install/uninstall prompt without being suspicious.
No, Market is not a safe place. Any developers can upload any program to Market, and Google does not screen those programs. However, Google will and do remove any reported rogue programs quite quickly.