Are you sure it was really deindexed by Google? Google this search query: site:domain.com. If your website appears in the results, it means it hasn't been deindexed.
Are you using blackhat tactics? Just changing your template will not cause a deindexing of your site in most cases but it might if your new template contains malware, in which case you would have received a warning.
Add your site to Google webmaster tools to check for any manual actions. If there aren't any, submit your site to Google using the 'fetch as google' tool within your WMT dashboard, then build a few links and wait to see if your site will be re-indexed.
Also, confirm that you aren't blocking Google from indexing your site using an online robots.txt checker (google it).