I haven't done any Android development in Linux, so my answer is based on my Windows experience, so to answer your first question last, yes. It can be done in Windows.
From what I've read / heard the following should be applicable to Linux as well.
Eclipse is definitely where you want to be building your Android applications from. Google have released a plugin (Android Developer Toolkit) that automagically integrates all the debugging tools, emulator, compiler, new project wizard, etc. You don't need it, but it makes everything much easier.
Both Eclipse and the SDK are download-unzip-run installations that should be straight forward to get running. If you haven't already, start by getting the latest Android SDK from [http://code.google.com/android/download.html'], just unzip it into a new development sandbox and take note of where you put it.
Getting Eclipse Setup
You can download a compatible Eclipse with all the libraries and tools you need for Android from here:
[http://www.eclipse.org/downloads/packages/']
The 'Eclipse IDE for Java Developers' package has everything you'll need. To install just unzip it into a new folder and run the Eclipse.exe
executable, let it create a new workspace wherever you like. Once you're in you'll want to install the Android plugin to make your life easier.
Select Help > Install New Software..., and in the dialog box the comes up enter https://dl-ssl.google.com/android/eclipse/.
into the 'work with' text entry box.
Hit OK and accept all the prompts until it's installed. Restart Eclipse and you're almost ready to rock.
Select Window > Preferences... and select Android, then put the folder where you unzipped the SDK into the SDK Location text box. Hit Apply then OK and you're done.
Getting Started
The Plugin creates a new Android project type in the New > Project... menu. Every new project is actually an implementation of 'Hello World' that can help get you started.
Before you can use the emulator you need to create a virtual device. An Android virtual device lets you specify a target Android platform, screen resolution, and hardware settings.
To create a Virtual Device select Window > Android SDK and AVD Manager. Click the 'New' button and select a name and target platform. In most cases you'll want to select the latest API Level with the Google APIs (Eg. Google APIs (Google Inc.) - API Level 4). Enter an SD Card size greater than 8M and select a skin / screen resolution depending on the device you wish to emulate. Select the 'Create AVD' button.
To run it up in the emulator hit the Run > Open Debug Window... menu option. The defaults should work just fine, so hit Debug and the default AVD should launch and show your new application.