Okay, I figured it out. Had to make a small tweak to the code in my form, and then add the handlers; one for the list box to add a handler to each item that's added to the list box, and one that will be used for the items themselves.

Code:
    Private _CycleJobItems As ObservableCollection(Of CheckedListItem(Of CycleJob))
    Public Property CycleJobItems() As ObservableCollection(Of CheckedListItem(Of CycleJob))
        Get
            Return _CycleJobItems
        End Get
        Set(value As ObservableCollection(Of CheckedListItem(Of CycleJob)))
            _CycleJobItems = value
            AddHandler CycleJobItems.CollectionChanged, AddressOf CycleJobItems_CollectionChanged
        End Set
    End Property

    Private Sub CycleJobItems_CollectionChanged(sender As Object, e As Specialized.NotifyCollectionChangedEventArgs)
        '# This means we're adding new items to the list.
        If e.NewItems IsNot Nothing Then
            For Each Item As CheckedListItem(Of CycleJob) In e.NewItems
                '# Add a handler for this item so that we can listen for the checkbox element
                '# being ticked or cleared.
                AddHandler Item.PropertyChanged, AddressOf CheckedListItem_PropertyChanged
            Next
        End If
        '# This means we're removing existing items from the list.
        If e.OldItems IsNot Nothing Then
            For Each Item As CheckedListItem(Of CycleJob) In e.OldItems
                '# Remove the handler for each item.
                RemoveHandler Item.PropertyChanged, AddressOf CheckedListItem_PropertyChanged
            Next
        End If
        '# Clearing the list doesn't provide an OldItems collections, so if the action is a reset and there's
        '# nothing in either collection, do whatever would happen if you removed each item individually.
        If e.Action = Specialized.NotifyCollectionChangedAction.Reset AndAlso e.OldItems Is Nothing AndAlso e.NewItems Is Nothing Then
            '# Do whatever
        End If
    End Sub

    Private Sub CheckedListItem_PropertyChanged(sender As Object, e As PropertyChangedEventArgs)
        '# Check that it was the IsChecked property that changed.
        If e.PropertyName = "IsChecked" Then
            Dim Item = TryCast(sender, CheckedListItem(Of CycleJob))
            '# If the item was ticked, add it to the collection of selected jobs unless it's already there.
            If Item.IsChecked Then
                '# Do whatever
            Else
                '# Do whatever
            End If
        End If
    End Sub