With all the people out there willing to offer help on Linux, getting started should be pretty easy. But with many options in introductory books and easy-to-install distributions, choosing a place to start can be the hard part.
Picking a distribution gets a lot less challenging when you remember to choose based on where you plan to go for help. Your local user group mailing list will be a lot more useful when other members know the locations and utilities you're talking about. Just subscribe to your local user group mailing list, and lurk for a while to find out what distribution the most helpful people there use. Then pick up a copy of a good Linux book, burn an install CD, and jump in.
There is lots of useful online documentation for specific tasks. But so far, books offer the best introductions to basic concepts such as file permissions or working with the shell. And looking for the distribution's name in the title of your first Linux book can be a time and frustration saver for new users. Instead of telling you to do things this way on one distribution, that way on another, or worse, telling you to find things for yourself, a book that concentrates on one distribution can point you straight to the file, tool or feature you need.
Lately, though, there's been a catch. The most helpful introductory books for beginners, Mark G. Sobell's "Practical Guide..." series, cover Red Hat Linux and its descendants Fedora and Red Hat Enterprise Linux, but many of the participants in user groups and mailing lists that offer the best help for new users are running Ubuntu. Sobell's new A Practical Guide to Ubuntu Linux closes the gap.
Part of Ubuntu's popularity among user group members is because it nails down and documents many of the best system adminstration practices. For example, many administrators recommend that you never log in as root. Just log in as yourself, and use a properly configured sudo to run individual commands as root when needed. Ubuntu actually disables the root account, and forces you to use sudo.
A new user who installs Ubuntu and does things the Ubuntu way will find himself or herself acting in many ways like a cautious, experienced sysadmin without realizing it. Now, in A Practical Guide to Ubuntu Linux, you can get a thorough Linux intro book that works the Ubuntu way, while still drawing on the author's long experience with old-school Unix and older Linux environments to cover the basics that haven't changed.
One tool that gets too little coverage in most Linux books for new users is OpenSSH. As the administrator of Linux servers, you'll use it for all kinds of remote administration tasks. This book, though, gives it a whole chapter, which should get you started on managing keys, logging in securely without a password, tunneling protocols that you want to secure, and other essentials. (If your first new Ubuntu box is a server, and you'll be ssh-ing in from your non-Linux system , check Rick Moen's ssh client list for the software you'll need on that end.)
Sobell covers the new Upstart init system, featured in Ubuntu 6.10 and later. If you have never set up services to run automatically at boot, upstart is a more featureful way to do it than the old Unix System V-based init scripts, but much of what you read in a book about Unix, or other Linux distributions, won't work. For example, you can't just put a line in /etc/inittab to have init restart a program if it dies. A Practical Guide to Ubuntu Linux will save you some time over learning init the old way, then discovering that you have Upstart instead.
Besides chapters on the basics, there are good introductions to server tasks such as mail, file server setup, firewalling and NAT, and web serving. Yes, this is a good intro for learning Linux at home, but you can make your Linux box at work earn its keep without going back to the bookstore. A shell scripting chapter will help you even if you don't plan to automate any of your own tasks that way yet--you'll probably need to figure out someone else's shell script at some point.
One of the most important Linux tools for new adminstrators, nmap, gets only a brief mention. Running nmap is a useful habit to make sure that you're running the server software that you think you're running, or that a firewall is set up correctly. I use it to check firewall and network address translation setups--it would have been helpful to mention nmap in the chapter on firewalling and NAT.