From the Square Enix account management page:

1. Select Service
2. PlayOnline / Final Fantasy XI
3. "Options List" for your PlayOnline ID
4. Update PlayOnline Mail Password

Changes will take effect immediately.