Changing “submitted on date” of comments

I presume you mean the format of the date that is displayed for the comment.

Different themes will do this different ways, but in general there should be a comments.php file which should contain what makes up a comment.

In here should be wp_list_comments();

You will need to add a callback in here which will allow you to override the comment functionality and create your own from scratch.