Assuming you have Spring 2.0 with the aop style config that is a breeze.
Code:
<aop:config>
<aop:pointcut id="interface1" expression="exectution (* YourInterface1.*(..))" />
<aop:pointcut id="interface2" expression="exectution (* YourInterface2.*(..))" />
<aop:advisor pointcut-ref="interface1" advice-ref="interface1-advice"/>
<aop:advisor pointcut-ref="interface2" advice-ref="interface2-advice"/>
</aop:config>
Classes implementing 1 of the 2 interfaces will have 1 advice added, classes implementing both interfaces will have both advices added. The same should be possible with old-style configuration but probably more verbose...