As I understand it, there are two different kinds of Internet Fax Provider:
a. those that work through the Windows Fax mechanism and provide a special
piece of software that behaves like a fax printer
b. those that work entirely through e-mail and expect you to send an email
to e regular e-mail address that happens to contain the fax number you want
to send to

A brief look suggests efax/j2 is type (b) and, if so,
c. you should not need to install anything or configure anything in Word or
Outlook
d. in Outlook, you should only have to get the e-mail address right
e. in Word, you should "Send to"|"Mail Recipient (as Attachment)" and
provide the correct e-mail address (as in (d), rather than trying to send
via the "Send to"|"Recipient using Internet Fax Service" option.

I think...

If none of that helps,
a. which version of Windows and Word
b. are you using Outlook (not Outlook Express)?
c. which fax service?