In reference of research (1996-97) during my residency at California State Polytechnic University, Pomona (College of Agriculture) Horticulture Department:
Canary Island Date Palm (Phoenix canariensis)
How to Propagrage Palm Seeds:

Palm Seeds of this variety were collected during the Fall and Winter months in Los Angeles County, and propagated at the College of Agriculture Horticulture Department at Cal Poly Pomona greenhouse placed on top of the facilities bottom heat unit, which temperatures ranged from 70-85º F.

Step 1
Collect Fruits (bright orange that fades to brown, left photo) from a viable source.  Phoenix varieties are known to naturally hybridize 

Step 2
Peel fruits (ideally when the fruit is brown it is much easier to peel covering) to expose the seed (light brown, right photo) 

Step 3
Space each seed 1" apart on about 3" of Coconut Fiber (loose soil mix) in a Ziplock bag (see photo below).

Step 4
Cover seeds with 1" of the Coco Soil Mix, and watered thoroughly.

Step 5
Close Ziplock bags to create a natural greenhouse with the zip plastic bags and place in shelter (i.e. house, greenhouse) on a propagation heat mat, or outside (preferable tropical or sub-tropical climates) in indirect sunlight. 

End Results
For this palm variety (P. canariensis), 8-10 weeks seedlings should emerge about 1-2" long foliage, which for myself I had a 88.9% success rate (see photo and test results below).  
Exterior Propagation Notes:
If seeds are grown outdoors: tropical and subtropical climates are preferable; place in indirect sunlight, but naturally heated areas for a higher success rate.
Step 3
End Results
Palm Propagation
Propagation Growing Process
Test Results

Test #1 (9/18/96 - 12/3/96)
42 of 46 seeds propagated, 2 bags (95.7% success rate)

Test #2 (12/3/96 - 2/4/97)
158 of 160 seeds propagated, 5 bags (98.8% success rate)

Test #3 (11/5/96 - 2/4/97)
19 of 20 seeds propagated, 1 bag (95% success rate)

Test #4 (1/10/97 - 3/19/97)
222 of 270 seeds propagated, 6 bags (82.2% success rate)

Total Results = 441 of 496 succeeded (88.9%)