What you want to do is create a spatial join in QGIS.
Load your two shape files into QGIS. Then select Vector->Data Management Tools->Join Attributes by Location. Select your district layer as the Target Vector Layer, your provinces layer as Join Vector Layer. For Attribute Summary select "Take Attributes of first located feature". Select your output layer. For Output Table, select "Only Keep Matching Records". If the polygons are accurate, it shouldn't matter which value you select for Attribute Summary or Output Table.
The result of this operation will be a new layer with as many rows as your district layer. Each row will contain all the fields of the district layer PLUS the fields of the Province layer. You can then delete any unneeded fields that were inherited from the Province table (presumably everything except the province name or id).
Your first sanity check is that the output layer should have exactly as many rows as your input (Districts) layer. The more difficult check is that the district is in the right province. If the boundaries of the two layers don't quite align, a district might be seen as being in two different provinces, and the join will select the first one seen. One way to address this to add a new integer field to the provinces layer. Call it something like "Verify". Set this field to 1 for every record. When doing the join, set the Attribute Summary to "Take Summary of Intersecting Features" and select "Sum". Then when you're checking the resulting join, look for records where the Verify field is greater than 1. These are the records you need to check and perhaps fix manually.
An alternative approach that directly deals with districts intersecting multiple provinces is by selecting the province with the greatest area in the intersection. The best I could come up with is to use Vector->GeoProcessing->Intersect to intersect all the districts with all the provinces, then take the ratio of the area of the intersection to the area of the district. (This requires you have an area field in each of the two input tables.) There's a sharp cutoff between those that are nearly 1 and those that are nearly 0. Delete the ones that are nearly zero, which should leave a table with districts and provinces. Note this table is NOT the correct answer yet - since these districts are the result of the intersection with provinces, so it's not the same as your district input file. I would then delete all fields in the intersection table except the district ID and the province ID, then do an ordinary join on the district ID field with your original district table.
(Sorry for this somewhat rambling answer, but I'm trying to figure out how to do this as I go.)
