How should I implement an alternative file upload? I want to write a module for Drupal 7 to integrate http://filepicker.io's awesome functionality. It's a simple JS widget that returns a URL of where the file is hosted.

I've never written a D7 module before, though I've written several for D6.

Should I create this as a fields widget (and if so, for which fields- file/image/link?), or should I create a whole new field type for this?

In production, my intent is to mix up the types a bit with this; that is, we have lots of images uploaded already, I'd just like to upgrade the 'upload' button (in lay terms) without breaking everything.
If you want it to use http://filepicker.io's storage, it will definitely be link field. It's your own design decision if you will just add a widget (that's what I would do) or clone it and add that widget to a clone. However, don't expect seamless work from images on your own domain and images stored away of it - you can't really resize, rotate, crop, generate thumbnails, and service may become paid one with only short notice (and unavailable without any notice at all).