To determine the grid reference, look for the bold numbers on the edges of the map. The eastings are along the bottom and top, while the northings are along the left and right.
The first 2 digits of the easting are determined from the large bold numbers at bottom of the map. The 3rd digit is determined by measuring the distance of the feature from the left edge of the grid cell which contains it, dividing it by the width of a cell, and then multiplying it by 10. e.g. if the feature is 32 mm from the left edge of the cell, and the cells are 40mm wide, then the last digit will be 32/40*10 = 8. For 1:25000 maps, a simpler way is to just measure the distance in mm and divide it by 4. A map overlay such as those available from MapTools make this much more convenient.
The digits of the northing are determined in a similar way.
If you want to determine the full easting and northing from the map, look for the small digits which appear in front of some of the bold numbers on the edge of the map. In the above example, they are 2 for the easting, and 63 for the northing, giving full coordinates of 272500 metres East, 6323300 metres North.
AGD66 and AGD84 are the datums that older maps were printed with. Before the introduction of GDA94, AGD66 was used in NSW, Victoria, Tasmania, and the NT. Meanwhile, Queensland, SA and WA mostly used AGD84. These two datums are almost identical for the purposes of bushwalking - differing by about 5 metres or less.
GDA94 is the new datum which current and future maps will be produced with. This datum produces coordinates which differ by about 200 metres from both AGD66 and AGD84.
To convert grid references from AGD66 to GDA94, a rough rule of thumb is to add 1 to the easting part and add 2 to the northing part. e.g. GR 717255 in AGD66 is GR 718257 in GDA94. For more accurate conversions, you can use my Convert Coords program.
Note: For most practical purposes GDA94 is equivalent to WGS84. WGS84 is the datum which all GPS units use internally. (More info about this is available here.)
Once your GPS is set up to use UTM, it will display positions such as:
56 274242 E 6313954 NTo convert these to a grid reference on your topographic map, look at the last 5 digits of each coordinate. i.e 74242 and 13954. Now, the first 2 digits in each number is the grid square where you are on the map, and the 3rd digit in each is the sub-square location. So, in this case your grid reference will 742139.
See also my FAQ for GPS units.
Some older grid references refer to the 1:250,000 miles maps, and 1:63,360 inch-to-the-mile army maps. Part of the old Sydney 1:250,000 map can be seen here.