You will only need a one basic function for the taxonomy, it’s really straightforward: register_taxonomy().
If you want to use a custom post type, it’s just as simple: register_post_type()
For the widget, it’s a little more complicated. You’ll need to look at how to register widgets, and saving values and such. All of that is covered in Justin Tadlock’s EXCELLENT tutorial. You’ll also probably need to look into WP_Query to query the posts, taxonomies and such.
That should get you going, if you have any specific issues implementing any of that, it’s probably better served in a separate question that defines the scope of your question more…well…specifically! 🙂