I have a table that has fairly heavy queries. The column I am joining on is an FK to a PK in another table. This column seems to take up of the query time with a table scan which leads me to believe that SQL Server won't be able to use the index on the remote table and will need it's own index on my source table.
I am fairly sure I am right but it would be great if a SQL Server 2008 genius could wade in on this.
Do you need to index Foreign Key columns? No, absolutely not.
Should you index Foreign Key columns? Almost certainly. As you've discovered Foreign Key columns are often used in SELECTs and JOINs, and unless indexed they can really kill your performance.
You should definitely have your Foreign Key column indexed! Some have argued that this should be done automatically by SQL Server.