Μπορείς να το κάνεις databind κάπως έτσι:
someCheckedListBox.DataBindings.Add(new System.Windows.Forms.Binding("DisplayMember", datasource, datamember));
someCheckedListBox.DataBindings.Add(new System.Windows.Forms.Binding("ValueMember", datasource, datamember));
To DisplayMember είναι αυτό που φαίνεται και το ValueMember είναι το ID του κάθε item.
To πρόβλημα είναι ότι το CheckedListBox δεν έχει ένα επιπρόσθετο property για να κάνεις databind και το checked status του κάθε item. Μπορείς να το φτιάξεις εσύ όπως εδώ: http://www.codeproject.com/cs/combobox/ExCheckedListBox.asp
Μια άλλη εναλλακτική λύση είναι να χρησιμοποιήσεις DataGridView με δύο columns, ένα για το check και ένα για το λεκτικό. Κατόπιν, μπορείς να αφαιρέσεις τα row και column headers έτσι ώστε να μοιάζει με CheckedListBox.
Vir prudens non contra ventum mingit