Sigh, the editor messed up on my last code snippet, it should look like this:

def menu_func(self, context):
    # Operators triggered by menus have their operator context by default set to
    #   EXEC_REGION_WIN. We need it set to INVOKE_DEFAULT to call invoke() instead of
    #   execute().
    self.layout.operator_context = 'INVOKE_DEFAULT'
    
    # Create the menu button
    self.layout.operator(AlignVerts.bl_idname, text="Align Verts")
def register():
    bpy.utils.register_class(AlignVerts)
    
    # Add "Align Verts" menu to the "Mesh->Vertices" menu.
    bpy.types.VIEW3D_MT_edit_mesh_vertices.append(menu_func)
def unregister():
    bpy.utils.unregister_class(AlignVerts)
    
    # Remove "Align Verts" menu from the "Mesh->Vertices" menu.
    bpy.types.VIEW3D_MT_edit_mesh_vertices.remove(menu_func)

Thanks for sharing.

I want to ask you where did you learn pythoning with Blender, and if there are any resources you'd recommend to the total beginner (good how-to guides, articles etc.).

Regards.

To answer my own question, after getting more around the Blender Foundation website you can find their Python guides:

http://wiki.blender.org/index.php/Doc:2.6/Manual/Extensions/Python

There must be several more sources (articles, tutorials, forums etc.) if you Google around, but the above one is the most "official".