I've mentioned the Team Foundation Version Control client API example before as good way to get started with the API, and there are examples with labels and items too.  You can find documentation for the classes and methods in the Team Foundation Version Control API in the October Visual Studio SDK release.  Once you install it, you can find the Version Control API doc in
C:\Program Files\Visual Studio 2005 SDK\2005.10\VisualStudioTeamSystemIntegration\Version Control\Object Model (Help 1.x format).zip.