AUとソフトバンクの携帯の普及端末の大半でCookieが利用できるようになってるみたいです。
AUはWAP2.0と呼ばれる端末、ソフトバンクは3GCと呼ばれる端末で利用できます。
正確な数字はわかりませんが、普及率は70%超えてるんじゃないでしょうかね?

PCと違ってちょっとややこしいこともあるのですが、
その代表として期限指定の方法について。

ソフトバンクはexpiresで日時指定をするのですが、
AUはMax-Ageで秒数で指定をします。
※Max-Ageについてはこのあたりの資料を。
http://www.m-fr.net/etc/cookie.html

踏まえて、下記のようなヘッダーで設定が可能です。

Set-Cookie: hoge=fooooooooooooooo;
expires=Mon, 28 Feb 2009 14:50:39 GMT;
Max-Age=3600;
path=/;
domain=xxxx.com;
\n


あとはドコモだけだよなぁ。