Make a sublime launcher .desktop file. I don't have one so I can't post exact instructions on that. You'll probably want to put it in /usr/share/applications/
System wide associations:
sudo sed -i 's/gedit.desktop/yournew.desktop/g' /usr/share/applications/defaults.list
Just your user's associations:
sed -i 's/gedit.desktop/yournew.desktop/g' ~/.local/share/applications/mimeapps.list
Edit from Oli. If you're using the PPA for Sublime Text 2, there is already a .desktop file for it sitting in /usr/share/applications/ so you can just run:
sudo sed -i 's/gedit.desktop/sublime-text-2.desktop/g' /usr/share/applications/defaults.list
Edit from trent. Running on 13.04, the above update didn't change the file association from gedit to sublime-text-2. It was necessary to update the file: /etc/gnome/defaults.list.
sudo sed -i 's/gedit.desktop/sublime-text-2.desktop/g' /etc/gnome/defaults.list