I'll focus on using IFERROR, since that's what you attempted.
If this column is just for an error flag, and you don't care what's displayed as long as you get the message when needed, you can use IFERROR. That returns the formula result as long as there isn't an error, or your message if there's an error. So using it with MATCH, you could do something like this. Assuming your values are in column A of both sheets, B1 of Sheet2 could contain:
=IFERROR(MATCH(A1,Sheet1!$A$1:$A$1000,0),"Add to Sheet1")
Use an appropriate range for Sheet1. This will display the "Add to Sheet1" message when needed, but will also display a number (the MATCH result) in other cases.
If you only want to see either the message or a blank cell, use IF and ISERROR:
=IF(ISERROR(MATCH(A4,Sheet1!$A$1:$A$1000,0)),"Add to Sheet1","")