WordPress.org

Will this plugin help me with Search Engine Optimization?

Nope. It could just improve your internal linking structure, and only if you don't use the Ajax version but it's not what the plugin has been designed for.

Is this plugin compatible with WP Super Cache?

Sure! When activating the widget in the sidebar, be sure to check the "Use Ajax Technology" checkbox and save. The plugin will appear in NON cached pages and will stay there also after pages are cached. If you want to see the plugin immediately on all your blog, refresh the cache.

If my theme does not support widget, or I want related posts displayed in a different position than the sidebar, how can I do?

Just paste this snippet in your theme where you want the box to appear:

<?php if (function_exists('SEQ_in_wp')) SEQ_in_wp(); ?>  

Remember you can edit the external css to change the box layout.
If your theme does not support widgets at all, you might want to wrap the snippet this way:

<div id="search-engine-query-in-wp">   
<?php if (function_exists('SEQ_in_wp')) SEQ_in_wp(); ?>   
</div>