Priority in Mail::Sender is just a header field 'X-Priority' with values from 1 to 5. So all you need is to set a header field:

# Email::Stuffer
$email->header( 'X-Priority' => 1 );

# Email::Simple
$email->header_set( 'X-Priority' => 1 );
[download]