チェックの状態を取得します。
CheckedListBox1_ItemCheckイベントハンドラをつかいます。
チェックされた場合は
e.CurrentValue = 0
チェックが外された場合は
e.CurrentValue = 1
になります。


CheckedListBoxの順番をフリーにする。
CheckedListBoxでチェックするときに下からチェックしても上からチェックしても、
演奏は上から演奏されるように、チェックされたインデックスのリストを作成します。
下からチェックされた場合のインデックスのリストをソートします。


CheckedListBoxのチェックの変化があったときはPlaylistをクリアしておきます。
CheckedListBoxのチェックの変化のたびにPlaylistにチェックされたファイルを
登録するため、チェックの変化があった場合はPlaylistをクリアします。


For文でループ
CheckedListBoxにチェックした数だけループして、CheckedListBoxにチェックした
項目のインデックスを取得して、そのインデックスを元にPlaylistにファイルを登録
します。


下記のコードのようになります。ループのところがややこしいですね。

Dim indexcount As Integer 　 'チェックしたインデックスの値の取得
Dim checindex As Integer 　 'チェックしたインデックス
Dim selectindx As New List(Of Integer) 　 'チェックしたインデックスのリスト
'チェックの状態
Private Sub CheckedListBox1_ItemCheck(sender As System.Object, _
e As System.Windows.Forms.ItemCheckEventArgs) Handles CheckedListBox1.ItemCheck

'CheckedListBox1で選んだファイルのインデックス
checindex = CheckedListBox1.SelectedIndex
'チェックされた場合リストに追加(Add)
If e.CurrentValue = 0 Then
selectindx.Add(checindex)
End If
'チェックが外された場合リストから削除(Remove)
If e.CurrentValue = 1 Then
selectindx.Remove(checindex)
End If
selectindx.Sort() 　 'selectindxを数字の小さい順にソートする（クイックソート）
'currentPlaylistのクリア
AxWindowsMediaPlayer1.currentPlaylist.clear()

Dim indexnum As Integer
'チェックしたインデックスのリストの数をカウントする
indexcount = selectindx.Count
For num As Integer = 0 To indexcount - 1
indexnum = selectindx(num)　 'チェックしたインデックスの値の取得

'AxWindowsMediaPlayer1に再生するファイルの登録
AxWindowsMediaPlayer1.currentPlaylist.appendItem _
(AxWindowsMediaPlayer1.newMedia(arnme(indexnum)))
Next

'停止のメソッド
dostop()
End Sub