Beforehand

With the currently used input driver system it is not possible to change the scroll speed of your mouse, at least not without drawbacks. You are able to adjust the scroll speed for Qt-Applications using a KDE Settings but the only current way to change the scrolling in a generic fashion is by using imwheel which seems to be problematic in many ways (see comments). In the future this will be fixed with libinput and the systemd hardware database.

Current Way

Install imwheel with the following command or from the Software Center:

$ sudo apt-get install imwheel

Create (if necessary) and edit the configfile ~/.imwheelrc with an editor of your choice (e.g. gedit). Fill in the following for increasing the scroll speed for every Command. NB: This configuration file will apply these new scroll settings to all programs, (including the terminal, which may not be what you want).

".*"
None,       Up,     Up,     3
None,       Down,   Down,   3

If you want to only apply these settings to Chrome, for instance, use these settings instead:

".*-chrome*"
None,       Up,     Up,     3
None,       Down,   Down,   3

The 3 is a scroll multiplier to increase the effectiveness of the scroll wheel. In the README of the project it is called "REPS". The readme states:

[ REPS ]

Reps (Repetitions) lets you say a number for how many times you want the output keysyms to be pressed. See the chart on the default bindings for the default number of reps for each modifier-combo (The chart is near the end of this document).

In other words, it is a scroll multiplier. If REPS is set to 3, that means that when your mouse wheel commands one scroll command, the software intercepts this command and sends 3 commands to the PC instead of 1, thereby making it scroll 3 times farther, or "faster".

For more information also take a look at the manpage:

$ man imwheel

or refer to the README of the project.

You can start imwheel by typing:

$ imwheel

Be sure that you don't start the imwheel twice! That's a known bug, but you can stop imwheel with the command:

$ killall imwheel

To get imwheel to automatically start every time your computer boots, you must add it to the startup menu AFTER an x-window is loaded. IMPORTANT: since imwheel relies on an x-window to already be running, it will NOT work if you add it to crontab, /etc/init.d, or /etc/rc.local. That means you must do it this way instead:

Ubuntu:
Use the "Startup Applications" GUI editor to Add imwheel as a Startup Program: https://askubuntu.com/a/48327/327339

Xubuntu:
Use the "Session and Startup" GUI editor --> Application Autostart --> Add to add imwheel as a startup program.

More screenshots here: https://askubuntu.com/a/369443/327339.

Future

This tutorial is currently under development.

libinput seems to be included with Wily Werewolf (15.10) where you need to install the package xserver-xorg-input-libinput. After you installed libinput with

$ sudo apt-get install xserver-xorg-input-libinput

it should be used for every input after you restarted the Xorg (logout would be sufficient). Now that you are using libinput you are able to adjust the settings of your mouse. You can find a full tutorial in the file /lib/udev/hwdb.d/70-mouse.hwdb. Let me cover here only the basics.

The following steps are need to be done as root. Because of that I am friendliy reminding you that everything you do you need to take responibility.

First get the vendor id <vid> and the product id <pid> using lsusb. Here with a MX 518 Logitech Mouse as example. If you have the following line in the output of lsusb.

Bus 005 Device 002: ID 046d:c051 Logitech, Inc. G3 (MX518) Optical Mouse

The <vid> is 046d and the <pid> is c051.

Then create a File that looks like the following with gksudo gedit /etc/udev/hwdb.d/71-mouse-local.hwdb

mouse:usb:v<vid>p<pid>:name:*:
    MOUSE_WHEEL_CLICK_ANGLE=??

For example this file for the Logitech MX 518 example above:

mouse:usb:v046dpc051:name:*:
    MOUSE_WHEEL_CLICK_ANGLE=30

This file sets the mouse wheel click angle to 30° (default is usually 15). To use this setting, update the hwdb with the following commands:

udevadm hwdb --update
udevadm trigger /dev/input/event${id}

One can figure out the ${id} using xinput (look out for the id of your mouse) and then run xinput list-props ${xinput_id}.

Note that using the ~/.imwheelrc recommended in the accepted answer does not actually increase the scroll wheel speed. Rather, it replaces scrolling with multiple arrow key strokes. This has the disadvantage of not being able to scroll a window until you change focus to it, not the default behavior. This answer aims to provide an alternative that behaves more closely to the native behavior.

To provide a concise answer for Ubuntu >14.04 (combining the answers from @tvm and @redanimalwar with the comment from @aroll605), it seems the best option to actually increase the scroll wheel speed is to install imwheel and configure it by following these steps:

1. Install imwheel by running:

   sudo apt install imwheel
   

   (replace apt with apt-get depending on your system)

2. Edit ~/.imwheelrc:

   gedit ~/.imwheelrc
   

   and paste:

    ".*"
    None,      Up,   Button4, 3
    None,      Down, Button5, 3
    Control_L, Up,   Control_L|Button4
    Control_L, Down, Control_L|Button5
    Shift_L,   Up,   Shift_L|Button4
    Shift_L,   Down, Shift_L|Button5
   

   You should try different values for # in the lines:

    None,      Up,   Button4, #
    None,      Down, Button5, #
   

3. To test the settings use the command:

   killall imwheel && imwheel -b "4 5"
   

4. Open Startup Applications and add:

   imwheel -b "4 5"
   

   Note that using the option -b "4 5" restricts imwheel to only affect the scroll wheel, discussed here.

// Edit

As this gets some upvotes from time to time: I not use this anymore (out of laziness after reinstalls) and I now think this script the slider and stuff is too much overhead. Also people have pointed out issues with this over time. So as a minimalistic guy I now created the config myself. Its probably a one time thing for most people.

I have edited this to be a 4 step guide with everything you need.

And another update: Since I switched to KDE, that actually has a setting for this and a million others things Gnome does not (Not even realized how much i missed KDE). The issue is that KDE mouse settings have actually have no effect on Firefox (and other GTK apps I assume) but since my main purpose for this was actually web browsing I now found out that you can actually tweak how much the mouse scrolls in Firefox itself.

about:config
mousewheel.default.delta_multiplier_y

I set it to 600 and its perfect for me

// End Edit

The accepted answer has a config that for whatever reason maps the scrolling to UP and DOWN on the keyboard. Makes no sense to me.

I have found a perfect script that actually maps to the mouse and adds a GUI to set up the mouse speed.

#!/bin/bash
# Version 0.1 Tuesday, 07 May 2013
# Comments and complaints http://www.nicknorton.net
# GUI for mouse wheel speed using imwheel in Gnome
# imwheel needs to be installed for this script to work
# sudo apt-get install imwheel
# Pretty much hard wired to only use a mouse with
# left, right and wheel in the middle.
# If you have a mouse with complications or special needs,
# use the command xev to find what your wheel does.
#
### see if imwheel config exists, if not create it ###
if [ ! -f ~/.imwheelrc ]
then

cat >~/.imwheelrc<<EOF
".*"
None,      Up,   Button4, 1
None,      Down, Button5, 1
Control_L, Up,   Control_L|Button4
Control_L, Down, Control_L|Button5
Shift_L,   Up,   Shift_L|Button4
Shift_L,   Down, Shift_L|Button5
EOF

fi
##########################################################

CURRENT_VALUE=$(awk -F 'Button4,' '{print $2}' ~/.imwheelrc)

NEW_VALUE=$(zenity --scale --window-icon=info --ok-label=Apply --title="Wheelies" --text "Mouse wheel speed:" --min-value=1 --max-value=100 --value="$CURRENT_VALUE" --step 1)

if [ "$NEW_VALUE" == "" ];
then exit 0
fi

sed -i "s/\($TARGET_KEY *Button4, *\).*/\1$NEW_VALUE/" ~/.imwheelrc # find the string Button4, and write new value.
sed -i "s/\($TARGET_KEY *Button5, *\).*/\1$NEW_VALUE/" ~/.imwheelrc # find the string Button5, and write new value.

cat ~/.imwheelrc
imwheel -kill

There is also a video where it is introduced. I have not even finished watching this because I got it running in no time. The following would install the required packages, download the script and execute it for us:

sudo apt-get install -y imwheel
wget http://www.nicknorton.net/mousewheel.sh ~/bin/set-mousewheel
chmod +x ~/bin/set-mousewheel
~/bin/set-mousewheel

Set the wheel speed on a nice slider and be happy. Later just change with set-mousewheel command.

Not sure if imweel is automatically started after install, else we need to add it to startup applications.

My two cents: my Microsoft Sculpt Ergonomic mouse was scrolling about half a page at a time on Ubuntu 15.04 (Lenovo ThinkPad x220), which was really annoying me. I tried various solutions, but ended up having the idea of disconnecting the mouse from the USB port (the wireless dongle thing) and reconnecting it. Voila!..."normal" scrolling speeds ensued :). Hope that helps somebody.

While the above imwheel suggestions helped a bit, I found that removing the mechanical scroll-clicking mechanism made my mouse wheel much more pleasant to use -- not only removing the click, but making it faster and more precise to control!

And it only took 3 minutes - check out these instructions:

http://www.instructables.com/id/Making-a-mouse-wheel-not-click./

In a nutshell, you're removing this left spring (be careful to get the right spring back in place exactly):

Note: I have a standard, cheap mouse - a Logitech B100, others report success on similar models. Your mileage may vary.

imwheel will emit double scroll events in chrome, which is annoying

For i3wm and libinput users, I suggest libinput_patch, which gives an entry to change scroll delta in real time, and is much better in my use case

I also wanted to increase the mouse scroll wheel acceleration, and not just the absolute speed. This is a feature in MacOSX but not builtin for Xorg (also Wayland) yet.

I implemented such a feature in user space here (mouse-scroll-wheel-acceleration-userspace). This will increase the scroll speed, or accelerate the scroll speed. You would just run this in the background, with your preferred options. The code is quite simple Python code, and should be easy to modify as well.

Installation:

# get the tool
git clone https://github.com/albertz/mouse-scroll-wheel-acceleration-userspace.git
cd mouse-scroll-wheel-acceleration-userspace

# install Python dependencies
pip3 install --user -r requirements.txt  # (basically pynput)

# run the tool
./main.py -v --exp 1  # example flags. see --help
# (leave this running in background)

I just searched for this problem, because after a reboot my mouse wheel got really slow. After trying to solve it with different applications (imwheel, ...) I just unplugged it and plugged it in again and it worked like before. So if the speed changed between restarts without you doing anything, this might be worth trying.

I modified mousewheel.sh in order to include horizontal scroll speed adjustment:

#!/bin/bash
# Version 0.1 Tuesday, 07 May 2013
# Comments and complaints http://www.nicknorton.net
# GUI for mouse wheel speed using imwheel in Gnome
# imwheel needs to be installed for this script to work
# sudo apt-get install imwheel
# Pretty much hard wired to only use a mouse with
# left, right and wheel in the middle.
# If you have a mouse with complications or special needs,
# use the command xev to find what your wheel does.
#
### see if imwheel config exists, if not create it ###
if [ ! -f ~/.imwheelrc ]
then
cat >~/.imwheelrc<<EOF
".*"
None,      Up,   Button4, 1
None,      Down, Button5, 1
Control_L, Up,   Control_L|Button4
Control_L, Down, Control_L|Button5
Shift_L,   Up,   Shift_L|Button4, 1
Shift_L,   Down, Shift_L|Button5, 1
EOF
fi
##########################################################
CURRENT_VALUE=$(awk -F '[|]Button4,' '{print $2}' ~/.imwheelrc)
NEW_VALUE=$(zenity --scale --window-icon=info --ok-label=Apply --title="Wheelies" --text "Mouse wheel speed:" --min-value=1 --max-value=100 --value="$CURRENT_VALUE" --step 1)
if [ "$NEW_VALUE" == "" ];
then exit 0
fi
sed -i "s/\($TARGET_KEY *Button4, *\).*/\1$NEW_VALUE/" ~/.imwheelrc # find the string Button4, and write new value.
sed -i "s/\($TARGET_KEY *Button5, *\).*/\1$NEW_VALUE/" ~/.imwheelrc # find the string Button5, and write new value.
cat ~/.imwheelrc
killall imwheel ; 
imwheel
imwheel -kill -b "4 5"

Added 3rd and 2nd last lines in order to kill and restart imwheel process on manjaro/arch, remove them if they cause bugs on ubuntu.