<p>Is there a way to search Microsoft Visual SourceSafe 6.0d for all files tagged with a specific label?</p>

I don't think you can search by label, but you can get by label.
From MSDN:
To get a version by label:
Make sure that you have set a working folder in Visual SourceSafe Explorer. See How to: Set the Working Folder.
Ensure that you have set the history options. See How to: View History.
Select the project that contains the file to retrieve.
On the Tools menu, click Show History.
In the History Options dialog box, select the version of the file to retrieve and click OK.
In the History of  dialog box, click Get to retrieve the version of the file that you have chosen.
In the Get dialog box, make any additional entries needed and click OK to retrieve the file.