To use the avrisp mkII and other programmers run on Linux needed to add a rule to udev (according to this http://www.mikrocontroller.net/articles/AVRDUDE)
Add a rule 10_avrproggers.rules to /etc/udev/rules.d/ containing:
# Atmel AVR ISP mkII SUBSYSTEM=="usb", SYSFS{idVendor}=="03eb", SYSFS{idProduct}=="2104", GROUP="users", MODE="0660" # usbprog bootloader ATTRS{idVendor}=="1781", ATTRS{idProduct}=="0c62", GROUP="users", MODE="0660" # USBasp programmer ATTRS{idVendor}=="16c0", ATTRS{idProduct}=="05dc", GROUP="users", MODE="0660" # USBtiny programmer ATTRS{idVendor}=="1781", ATTRS{idProduct}=="0c9f", GROUP="users", MODE="0660"
then restart udev and you are done.
USBasp is natively supported on Ubuntu 10.04 and newer.