Accidently deleted /usr/lib, how do I restore it?

There are tools that might help you undelete the files, but usually it's a slow and mostly manual process. Search engines are your friends.

It may be easier to boot up a live CD or USB, mount your system's root partition, then copy /usr/lib to /mnt/{root.drive}usr/lib, but you will only get the default lib files and not what you may have added.

I think the best option is to reinstall the OS. Of course, you will want your data on a separate partition that is not formatted during install, good practice IMHO.

Supposing apt-get still works you can try to use dpkg to get a listing of the packages that have files there and then install them with apt-get. You can use this Ruby script, but the same idea can be implemented in python or bash:

raw_pkgs = `dpkg --get-selections`.split("\n")
need_reinstall = []

path="/usr/lib"

raw_pkgs.each do |x|
    pkg = x.split(" ")[0]
    if `dpkg -L #{pkg}`.include? path
        puts "-> #{pkg} has files in #{path}"
        need_reinstall << pkg
    end
end
puts "\nYou need to reinstall #{need_reinstall.size} packages:"
puts "\tsudo apt-get install --reinstall " + need_reinstall.join(" ")

It is a little of a brute-force solution and will take some time (in my system the listing was ~65% of the total packages installed...), but should work.