Links is a fairly complex program, but how hard it will be to install sort of depends on your particular host. Some hosts provide easy access to CGI, some don't. Read through whatever instructions your host gives you about using CGI, then contact them and ask questions if its not totally clear what you have to do. If you go slow and are patient while installing, you should be OK.
If you do have troubles, post a question in the forum that includes as much info about whatever error you are getting as possible (lots of very helpful folk around here!). Note that you will get more informative error messages if you run the offending script from the command line (telnet).
Here's a few tips off the top of my head:
1. Take extra care to be sure the location of perl is right for your server and all paths are correct. Using the full path to links.cfg often helps (at least it did for me!). When changing the .cgi and .pl files, be sure to use a plain text editor (like Notepad)--most HTML editors will fry them.
2. Upload all files in ASCII format...turn off any "auto detect" functions on your FTP program to be sure it doesn't send anything in binary format.
3. Change file permissions as you go and don't forget to change directory permissions as needed. Since there are a lot of files, you may find it helpful to make a list of what permission you gave each one and the directory it's under (so you can find them later!).
4. Be sure the LWP directory is all uppercase letters (Win 95-if thats what you're using- goofs the unzip...manually change it on the server).
5. Use the templates! They are a lot easier to customize and you won't have to deal with the site_html.pl script. Also note that the link to the CSS file is messed up in some of the templates and you will need to fix it. If you don't want to use CSS, take that link out of the header of every template.
6. Note that all <%if...%> and <%endif%> statements MUST be on lines by themselves. Many WYSIWYG editors mess this up by putting other HTML code or text on the same line (Frontpage is a prime offender). If something doesn't display right, check this first.
I hope some of that's helpful. As for your second question, yes you do need to be online to add links. Some people have mentioned using Excel to import data to the links.db, but I've never done this. If you're good with Excel and have a bunch of existing links you want to change to Links2.0, search the forum for "Excel" for more info.
