Did you add the plugins you tried to game.txt? For any plugin you use, you have to add it to vsh.txt, game.txt, or pops.txt if you want to use the plugin on the XMB, while playing games, or while playing ps1 games, respectively. They won't show up in the recovery menu otherwise.
Here's an example of what game.txt should look like, if you want to use a plugin for save states and nothing else.
Code:
ms0:/seplugins/pspstates_kai.prx 1
Personally, I use this:
http://dl.qj.net/down/psp-states-menu-pict-v3-save-with-graphical-style.html
Since states_menu_pict.prx activates the pspstates_kai.prx plugin by itself, all you need in game.txt is "ms0:/seplugins/states_menu_pict.prx 1". Of course, you'll need to have both files in the seplugins folder of your memory stick, and probably that ini file that comes with it as well.