I changed permalinks to some of my posts. A few days later, I noticed that these posts could not be found on google's search anymore. How can I fix this?
You can setup a 301 redirect from the old URL to the new URL. http://www.google.com/support/webmasters/bin/answer.py?answer=93633
you already know that you will need to do a 301 redirection. just google for 301 redirect and you will find the codes you will need to update your htaccess file. once you setup the htaccess file and upload to your server, google will follow the old URLs and land on the new ones upon which google index will be updated with the new URLs as permanent move from the old ones
301 redirect should've been setup the moment those pages were moved. It might be a tad bit tough to get them back up there now.