一番簡単なのはWindows付属のペイント、これでも一応壁紙はできますが機能が少ないので将来加工壁紙を作りたいと思ってる方にはあまりおすすめできません。
無料・そこそこの機能・操作が簡単なソフトはGoogleで「壁紙作成 フリーソフト」と入れれば結構な数が出てきますので時間のある方はそちらのほうがオススメ。
起動したら大抵のソフトは編集⇒貼り付け(ペースト)で貼り付けることができると思います。

貼り付けた画像を自分の作りたい壁紙サイズに収まるように大体の検討をつけて縮小し、そのあと目的の画像サイズに切り抜きます。
最近の機種はほとんどQVGAなので横240x縦320ドット(Win??CA機種なら240x400)にしとけばまず問題ないでしょう。
ふぃる(フォトショ)の場合はまず新規作成でキャンバスサイズを240x320にし、そこに画像を貼り付けてから縮小するという手順でやってます。
・作る時のコツとして、なるべく顔を大きく取ったほうが綺麗な印象の壁紙になると思います。
縮小を思いっきりかけて全身をいれてもいいのですが、携帯の画面ってちっちゃいですから肝心の顔がよく見えねーってことにもｗ；

そのまんま保存です、PNGでもGIF形式でも構いません。
・このときプログレッシブJPEG形式になっていると携帯でみれませんので注意。

色合いとかを鮮やかにしたり、背景色と立ち絵CGの色合いがマッチするように全体の色を修正します。
ちょっと彩度(色の鮮やかさ)をいじるだけでもかなり印象が変わりますのでお試しあれ♪
細かい部分はPC版缶詰めに載せてますのでよかったら参考に。

壁紙のアクセントに文字を入れます。
適当な文章を英文にして小さめのフォントで入れるだけで割とそれっぽいのができちゃったりします。
・Century Gothicとかシンプルで見た目もいいのでふぃるもよく使ってます。

加工壁紙のメインですね。
レイヤー機能がある画像ソフトが前提になるのでソフトの使い方がやや難しくなると思います。
透明度(α値)をいじったりうまい配置を考えたりと加工壁紙で一番頭を使う所であり、また一番作ってて楽しい所です♪

基本編にあるトリミングではなくここではイベントCGから立ち絵部分を切り抜きます。
一般に普通の立ち絵CGよりイベントCGのほうが壁紙向きな画像であることが多いので壁紙作りになれてきたら挑戦してみるといいかもです。
イベントCGから切り抜く一番のメリットは自分の好きな背景と合成できることですね。
基本的には大雑把に切り取ったあと４〜１０倍程度にルーペで拡大しながら細かい部分を消しゴムツール(ブラシ形状推奨)でチクチク消していきます。
簡単なものだと1枚10〜15分程、細かいCGだと1枚30分以上かかることもあります。慣れと根気が結構いりますね。
・コツとして切り抜きは縮小前の画像でやることです。多少ミスっても縮小したらほとんど分かりませんｗ
フォトショではマジック消しゴムという同系統の色をまとめて消してくれるツールがあるので割と楽に切り抜けますが、細かい部分はやはり手動で消す必要があります。