Force CKEditor to add a class to p-tags

You can add html processor filter

editor.dataProcessor.htmlFilter.addRules({
    elements :{
        p : function( element ){
            if ( element.className.indexOf("thiny_p") < 0){
                element.className += 'thiny_p';
            }
        }
    }
});

Also, if it is not required to be created as ckedito plugin maybe before you send content to server you can use jQuery to change content

$("iframe", "#cke_editor1").contents().find("p").addClass("tiny_p");

or, if textarea (source) is active

var editor= $("textarea", "#cke_editor1"); 
editor.val(editor.val().replace(/<p>/gi, "<p class='thiny_p'>"))

you should tweak a bit .replace(/<p>/gi, "<p class='thiny_p'>") regular expression to support other cases.

EDIT

Finally got time to download and setup editor on my box, here is working plugin

CKEDITOR.plugins.add( 'customparagraph',
{
    init: function( editor )
    {
        editor.addCommand('addParagraphClassName',{
            exec : function( editor ){    
                var ps = editor.document.$.getElementsByTagName("p");
                for (var i=0; i < ps.length; i++){

                    if(ps[i].className.indexOf("thiny_p") < 0){
                        ps[i].className += "thiny_p";
                    }

                }

            }
        });

        editor.ui.addButton( 'ThinyP',{
            label: 'Appends thiny_p class',
            command: 'addParagraphClassName',
            icon: this.path + 'images/icon.gif'
        });
    }
} );

put it in plugins/customparagraph/plugin.js also create icon image plugins/customparagraph/images/icon.gif

in configuration you will have to add following configuration options config.js of you CKEdito installation

CKEDITOR.editorConfig = function( config )
{
    config.extraPlugins = "customparagraph";
    config.toolbar = [ [ 'ThinyP' ] ]; // add other toolbars and keep in mid this can be overwritten in page which loads CKEditor
};

OR

in page which loads CKEditor

<script type="text/javascript">
//<![CDATA[
    // Replace the <textarea id="editor1"> with a CKEditor
    // instance, using default configuration.
    CKEDITOR.replace( 'editor1',
        {
            extraPlugins : 'customparagraph',
            toolbar :
            [
                [ 'Bold', 'Italic', '-', 'NumberedList', 'BulletedList', '-', 'Link', 'Unlink' ],
                [ 'ThinyP' ]
            ]
        });
//]]>
</script>

User will have to click on toolbar button before save

Well .. not sure if you need that for some specific reason .. but wouldn't life be much easier if you do what you want to do at the display end?

Like if I display some text (saved from ckeditor) at the front end, display in something like a

<div class="ckcontent" > ... </div>

And all

 <p>

tags within it can be applied styles or applied jquery by the notation:

 .ckcontent p { margin-left:5px;........ }

OR

 $('.ckcontent p').addClass('ckparagraphs');