Starting from scratch can be painful. Luckily there’s a tool out there that can help: PyQGIS Plugin Builder. The form will build a minimal plugin for you. You’ll get a ready QGIS 1.0 plugin that implements an empty dialog with Ok and Close buttons. You can find a step-by-step description on how to create and modify this dummy plugin at linfiniti.com – “A simple QGIS python tutorial”.

From there, I suggest moving to the PyQGIS Cookbook – a great resource for everything related to QGIS with Python – especially the part about “Developing Python Plugins”. Tim also created a PDF version of the Cookbook (original post) if you prefer it in hard copy.